//选择、插入、冒泡、快速、归并、希尔、堆、计数、基数、桶排序 这10种经典的内排序算法及其衍生算法，得烂熟于心
//算法性能评判的准则包括时间复杂度、空间复杂度、常数项、稳定性
//排序算法分为线性算法和非线性算法，把时间复杂度为O(N)的算法称为线性算法
//各算法的公认性能参照 https://blog.csdn.net/opooc/article/details/80994353
//N!>x^n>…>3^n>2^n>N^x>…>N^3>N^2>NlogN>N>logN>1
/
数据是随机整数，时间单位是秒
数据规模|快速排序 归并排序 希尔排序 堆排序
1000万 | 0.75 1.22 1.77 3.57
5000万 | 3.78 6.29 9.48 26.54
1亿 | 7.65 13.06 18.79 61.31
/
//1.系统的sort 方法，发现传进来的值为数值型，会使用快排，如果发现传的还有比较器，会使用归并排序
//2.归并和快排哪种更快？
// 快排比归并排序的常数项要低，所以要快。
//3.为什么会有归并和快排两种呢？
// 在比较的时候，使用比较器的时候，要追求一个稳定性，使用 归并排序 可以达稳定性的效果；使用快排不能够实现稳定性的效果。
//4.面对大规模的时候，当排序量是小于等于60的时候，sort方法 会在内部使用插入排序的方法（不一定是60，是一定的规模）当数据量很低的时候，插入排序的常数项低。
//5.在c语言中有一版，把归并排序，改成非递归，是基于工程其他考虑。
//6.预防快排在数据有序时表现的N**2的时间复杂度，算法导论提出，用一个按特定规则取出的中位数作为pivot比较合适，这个规则为按照3或5个数一组取出它们的中位数，再在这些中位数中按同样的方法去除最终的那个总的中位数，即是第一轮的pivot，pation后按此方法递归左右两部分。
//7.稳定的排序算法：冒、插、归的三种标准写法+3种线性排序，选择排序为不稳定

冒泡

  1. //经典冒泡
  2.         void bubble(int arr[], int len) {
  3.             for (int i = 0; i < len; ++i)
  4.                 for (int j = 1; j < len - i; ++j)
  5.                     if (arr[j - 1] > arr[j]) exchange(arr, j - 1, j);
  6.         }

外层优化

//用一个flag来判断一下，当前数组是否已经有序
        void bubbleI(int arr[], int len) {
            for (int i = 0; i < len; ++i) {
                bool isOrder = true;
                for (int j = 1; j < len - i; ++j)
                    if (arr[j - 1] > arr[j]) {
                        exchange(arr, j - 1, j);
                        isOrder = false;
                    }
                if (isOrder) return;
            }
        }

内层优化

//用一个pos来记录上一轮冒泡中最后发生交换的位置
void bubbleII(int arr[], int len){
     int isOrdered;
    int right=len;
    int currentRight;
    for(int i=0;i<len;++i){
        isOrdered=true;
        for(int j=1;j<right;++j){
            if(arr[j-1]>arr[j]){
                swap(arr,j-1,j);
                isOrdered=false;
                currentRight=j;
            }
        }
        if(isOrdered) return ;
        right=currentRight;
    }
}

插入排序

void insert(int arr[],int len) {
    for (int i = 1; i < len; ++i)
        for (int j = i; j > 0; --j){
            if (arr[j - 1] > arr[j]) 
                exchange(arr, j - 1, j);
            else
                break;
        }
}

选择排序

void select(int arr[],int len) {
    for (int i = 0; i < len; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < len; ++j){
            if (arr[minIdx] > arr[j]) 
                minIdx = j;
        }
        exchange(arr, i, minIdx);
    }
}

快速排序

本质上是二叉树的先序遍历

void quick(int arr[], int len) {            
    if (len < 2) return;
        quickSort(arr, 0, len - 1);
    }
}
//quickSort
        void quickSort(int arr[], int left, int right) {
            if (left < right) {
                srand(time(0));
                int random = rand() % (right - left + 1) + left;
                exchange(arr, random, right);
                int pivot = separate(arr, left, right);
                quickSort(arr, left, pivot - 1);
                quickSort(arr, pivot + 1, right);
            }
        }
        int separate(int arr[], int left, int right) {
            int base = arr[right];
            int i = left;
            int j = right;
            while (i < j) {
                while (i < j&&arr[i] <= base) ++i;
                arr[j] = arr[i];
                while (i<j&&arr[j]>=base) --j;
                arr[i] = arr[j];
            }
            arr[i] = base;
            return i;
        }

归并排序

本质上是二叉树的后序遍历

void mergeSort(int arr[], int len) {
    if (len < 2) return;
        mergeSort(arr, 0, len - 1);
}
//mergeSort
        void mergeSort(int arr[], int left, int right) {
            if (left < right) {
                int mid = left + (right - left) / 2;
                mergeSort(arr, left, mid);
                mergeSort(arr, mid+1, right);
                merge(arr, left, mid, right);
            }
        }
        void merge(int& arr[], int left, int mid, int right) {
            int* t = new int[right - left + 1];
            int i = left, j = mid+1;
            int k = 0;
            while (i <= mid&&j <= right)
                t[k++] = arr[i] > arr[j] ? arr[i++] : arr[j++];
            while (i <= mid) 
                t[k++] = arr[i++];
            while (j <= right) 
                t[k++] = arr[j++];
            for (int i = 0; i < right - left + 1; ++i) 
                arr[left + i] = t[i];
            delete []t;
        }

堆排序

根大堆用来求TopK小的元素，根小堆则是求TopK大的元素

分为初始化堆和维护堆两个操作

//根大堆排序法
        void heap(int arr[], int len) {
            if (len < 2) return;
            for (int i = 0; i < len; ++i)
                buildHeap(arr, i);//建堆
            int tail = len - 1;
            while (tail > 0) {
                exchange(arr, 0, tail);
                keepHeap(arr, 0, tail);//维护堆
                tail--;
            }
        }
        //往上走建堆
        void buildHeap(int arr[], int index) {
            while (arr[index] > arr[(index - 1) / 2]) {
                exchange(arr, (index - 1) / 2, index);
                index = (index - 1) / 2;
            }
        }
        //往下走维护堆，时间复杂度仅为log(N)
        void keepHeap(int arr[], int index, int size) {
            while (index * 2 + 1 < size) {//因为是完全二叉树结构，只要保证节点的左孩子有效既可，左孩子无效右孩子一定无效
                int leftChild = index * 2 + 1;
                int maxChild = leftChild;
                if (leftChild + 1 < size&& arr[leftChild + 1]>arr[leftChild]) 
                    maxChild = leftChild + 1;
                if (arr[index] >= arr[maxChild]) return;
                exchange(arr, index, maxChild);
                index = maxChild;
            }
        }

topk问题

include
1、nth_element 不排序，只做快选式partion
2、partition会分类但不排序
3、partial_sort 既partion也排序
4、自己写NlogK的堆排序