各种排序总结

非线性时间比较类

1. 交换排序

1.冒泡排序

思想：从前往后扫描，如果相邻两个元素的大小不满足要求，则进行交换。因此，每一轮可以将最大的元素放到最后一位，下一轮扫描时，就无需进行到最后一位了。

时间复杂度：进行两重循环，因此是O(n^2)

空间复杂度：原地排序，无需其他额外的空间，因此是O(1)

void bubbleSort(int array[], int length) {
        int t = 0;
        for (int i = 0; i < length - 1; i++){
            for (int j = 0; j < length - 1 - i; j++){
                if (array[j] > array[j + 1]) {
                    swap(array[i], array[j + 1]);
            }
        }
   }
}

2.快速排序

思想：快排的一个重要思想是递归。每一轮递归，需要选出一个基准元素（最好随机选取，下面附的代码是以第一个元素为基准元素），将大于此基准元素的放到其右侧；小于他的放到其左侧。然后左侧和右侧分别进行下一轮递归。

时间复杂度：由于快排能指数级的降低复杂度，因此是O(nlogn)

空间复杂度：O(logn)

void quickSort(int a[], int l, int r){
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = a[l];
    while(i < j){
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if(i < j){
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    quickSort(a, l, j);
    quickSort(a, j + 1, r);
}

2. 插入排序

1.简单插入排序

思想：维护前x个元素为有序的，当第x+1个元素要插入时，将其插入到合适的位置即可。

时间复杂度：O(n^2)

空间复杂度：O(1)

void insertSort(int array[], int length) {
        int current;
        for (int i = 0; i < length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
}

2.希尔排序

思想：首先把整个数组，分成若干个小组，然后对每个小组进行插入排序，由于小组的数据量小，因此插入起来效率较高。小组是通过增量来形成的。较简单的增量序列是[Lenght/2, Lenth/4 .....]，也有个别情景指定给出增量序列的。对于增量为Length/2时，小组为[0, length /2]、[1, length /2 + 1]......

时间复杂度：O(nlogn)

空间复杂度：O(1)

void sheelSort(int array[], int length){
    for(int gap = length / 2; gap > 0; gap >>= 1){
        for(int i = gap; i < lengh; i++){
            //将array[i]插入到此小组内合适的位置
            insertSort(array, gap, i);
        }
    }
}
//改写插入排序
void insertSort(int array[], int gap, int i){
    int value = array[i];
    int j = 0;
    for(j = i - gap; j >= 0 && value < array[i]; j -= gap){
        array[j + gap] = array[j];
    }
    arr[j + gap] = insert;
}

3. 选择排序

1.选择排序

思想：每一轮遍历，把最小的元素放到最前面。

时间复杂度：O(n^2)

空间复杂度：O(1)

void selectSort(int array[], int length) {
    for (int i = 0; i < length; i++) {
        int index = i;
        for (int j = i; j < length; j++) {
            if (array[j] < array[index]) 
                index = j; 
        }
        int temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
}

2.堆排序

思想：是利用堆这种数据结构来进行排序的算法。例如小顶堆，我们可以得到堆顶的最小值（根节点），将其与堆的最后一个元素交换，此时前n-1个元素可能不满足小顶堆的特性，因此让剩下n-1个元素重建一个小顶堆，则得到n个元素中的次小值。如此反复即可。

大顶堆：父亲节点的值大于其左右儿子的值。

小顶堆：父亲节点的值小于其左右儿子的值。

时间复杂度：O(nlogn)

空间复杂度：O(1)

void heapSort(int array[], int length){
    // 1. 将整个序列构建成堆
    // length / 2 - 1 是最后一个非叶子节点，只有非叶子节点才有调整的意义
    for(int i = length / 2 - 1; i >= 0; i--){
        heapAdjust(array, i, length);
    }
    for(int i = length - 1; i > 0; i--){
        // swap
        swap(array, 0, i);
        // adjust
        heapAdjust(array, 0, i);
    }
}

void heapAdjust(int array[], int i, int length){
    // 取出顶部元素
    int value = array[i];
    // 从左儿子开始
    for(int k = i * 2 + 1; k < length; k = k * 2 + 1){
        // 如果左儿子小，那么右儿子处更容易出现“儿子大于爹”的情况
        if(k + 1 < length && array[k] < array[k + 1]){
            // 切换至右儿子
            k++;
        }
        if(array[k] > value){
            array[i] = array[k];
            i = k;
        }
        else{
            break;
        }
    }
    // i 就是最后合适的位置
    array[i] = value;
}

4. 归并排序

1.二路归并排序

思想：将两个有顺序的数组合并成一个有序数组。

时间复杂度：O(nlogn)

空间复杂度：O(n)

void merge(int* a, int left, int right) {
    int* ta = new int[right - left + 1];
    int mid = (left + right) >> 1;
    int i = left, j = mid + 1;
    int pos = 0;
    // merge
    while (i <= mid || j <= right) {
        if (i <= mid && j <= right)
            ta[pos++] = a[i] > a[j] ? a[i++] : a[j++];
        else if (i <= mid)
            ta[pos++] = a[i++];
        else
            ta[pos++] = a[j++];
    }
    // copy
    for (int i = left; i <= right; i++) {
        a[i] = ta[i - left];
    }
    delete(ta);
}
void mergeSort(int* a, int left, int right) {
    if (left < right) {
        int mid = (left + right) >> 1;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, right);
    }
}

线性时间非比较类

1.计数排序

思想：计数排序的思想比较直观，从前到后，扫描下原序列，记录每个值下元素的个数，然后从最小值开始输出，如果此值对应的个数为2，那么输出两次就好。

如果数据的最小值，不是从0开始的，那么这个地方，在统计该值的个数时，可以减去最小值，整体的把数据平移一下。

在其他的排序场景下，例如统计学生的成绩，如果条件是成绩相同，我们需要保留原有数据的顺序，那么普通的计数排序无法保证保留原有顺序，他会打乱相同值的顺序（不稳定）。因此可以将其改进一下。

①用countArray数组统计每个值的个数

②countArray数组记录自己的前缀和，例如countArray数组为0、1、2、0、4，那么统计前缀和后就为0、1、3、3、7

③从后向前扫描原序列，通过其值v在value数组中找到对应的位置pos。位置pos=countArray[v]-1。在获得该位置后，countArray[v]--（这个地方很巧妙）。

计数排序不太适合数据较为离散的情况，以及小数的排序。

时间复杂度：O(n + m) m是最大值最小值之差

空间复杂度：O(m)

// 改进前的计数排序
void countSort(int* array, int length) {
    // 1 得到数列的最大值、最小值
    int maxt = array[0], mint = array[0];
    for (int i = 1; i < length; i++) {
        maxt = max(maxt, array[i]);
        mint = min(mint, array[i]);
    }
    // 2 countArray数组存储每个值的个数
    int *countArray = new int[maxt - mint + 1];
    // 3 遍历数列，获得每个值的个数
    for(int i = 0; i < length; i++)
        countArray[array[i] - mint]++;
    // 4 遍历统计数组，输出结果
    int index = 0;
    for (int i = 0; i < (maxt - mint + 1); i++) {
        for (int j = 0; j < countArray[i]; j++) {
            array[index++] = i + mint;
        }
    }
}

2.基数排序

思想：①分配根据关键字，把数组元素从前往后，分别装到相应的桶中，②收集，再从桶中收集回来。就以简单的数字排序为例，如果是个位、十位、百位的顺序，那就是最低位优先；与之相反，是最高位优先。

时间复杂度：O(N*K) K是关键字的个数

空间复杂度：O(n + m)

3.桶排序

思想：计数排序和基数排序中，都用到了桶排序的思想。桶排序是先根据数据中的最大值和最小值将数据划分区间，然后每个区间对应一个桶，每个桶中的数据可以通过归并排序、快排等方法再次进行排序。但是当数据的分布极其不均匀时，他的时间复杂度退化较厉害，用的较少。

时间复杂度：O(n + k)

空间复杂度：O(n + k)