这里列举一下常见排序算法的对比。
个人觉得相对重要需要会手写的排序算法还是快速、归并、堆排序、插入，以及借助桶(基数)排序了解桶的思想。
其他排序不常用，就是了解概念即可。

冒泡 Bubble Sort

  • 说明

    • 相邻元素的比较和交换来把小的数交换到最前面，过程类似水泡上升

    • 举例： 原始5,3,8,6,4，每一轮都是遍历N-1个元素，然后比较相邻元素，按大小关系交换，如下展示从尾部遍历的第一轮的过程

      1. 46比较： 5,3,8,4,6
      2. 84比较： 5,3,4,8,6
      3. …
      4. 第一轮结束： 3,5,4,8,6

      如此反复遍历全数据比较，直至某一轮没法发生交换即排序完成。

  • 复杂度
    • 最好： O(n) 原本有序，一轮结束
    • 最差，平均： O($n^2$)

*梳排序 comb sort

改进了冒泡排序，改进思想与下文希尔排序类似
比较少用，暂时不在这里说明了
复杂度有所改进，有兴趣可自己查阅其他资料，如梳排序 - 易百教程

选择 Selection Sort

  • 说明
    每次选使得一个元素找到他应该所在的次序位置。
    每一趟在剩余元素中选择最值，将其交换至应该存在的位置，直到所有元素排序完成。
    保证第i轮结束后，前i个元素有序
  • 复杂度
    • 最好、最差、平均：O($n^2$)
    • 但是一般性能优于冒泡，因为选择排序每一轮至多有一次交换，即最多n次交换，而冒泡交换是O($n^2$)级别的

插入 Insertion Sort

  • 说明
    基本操作是将一个元素插入到已经有序的数列中，从而得到一个新的有序数列
    实质是用增量排序操作去解决定量排序问题

  • 复杂度

    • 最好: O(n) 原本有序
    • 最差、平均: O($n^2$)

折半插入

靠二分去定位要插入的位置，但是后续多个元素的位移，仍旧是O(n)级别的操作
复杂度类似

希尔排序 Shell Sort

基本思想是将相距某个增量gap的记录组成一个子序列，通过插入排序使得这个子序列基本有序。然后不断缩小gap，gap以不断折半为规则。 总体复杂度为
图解如下：

复杂度

复杂度最终说法不一，可以明确的是 在O(N)和O(logN)之间，但是有些说是 O($n^{1.3}$) ，有些说是接近于O($NlogN$)， 我还没研究证明过

快速排序 Quick Sort

最常见的排序算法，各大基础库内置的基本都是这个算法。
采用分治思想，每次递归时选择一个点作为当前区间内的中点，将小于该中点的值放入左子树，大于该中点的放入右子树，然后继续对左子树和右子树进行相同的操作。 步骤描述如下：

  1. 从数列中挑出一个元素，称为 “基准”（pivot）
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

几种实现方法

实现的时候对于第2步的实现，有些trick的地方，直接按这个意思写写出来的代码性能会稍差，高效实现可以参看如下代码（均以顺序排序为例）：
下面代码中left和right都是指有效索引，即vec[left]和和vec[right]都有值

  • 取端点pivot的填充法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    template<typename T>
    void QuickSort(vector<T> &vec, int left, int right) {
      // 1 
      T pivot = vec[left]; //提出枢纽，这时left位置空出来了。
      int i = left, j = right;

      while (i < j) {//注意两个内层while的顺序不能换
          while (i < j && vec[j] >= pivot) j--; //这里是>=不能使>，否则当数组元素等于枢纽时会死循环
          vec[i] = vec[j];//将找到的小于于枢纽的元素存到j所指的空穴，这时j位置空出来了
          while (i < j && vec[i] <= pivot) i++; //这里是<=不能使<，否则当数组元素等于枢纽时会死循环
          vec[j] = vec[i];//将找到的大于枢纽的元素存到j所指的空穴，这时i位置空出来了
      }
      vec[i] = pivot;
      int pivot_pos = i;

      if (left < pivot_pos - 1) QuickSort(vec, left, pivot_pos - 1);
      if (right > pivot_pos + 1) QuickSort(vec, pivot_pos + 1, right);
    }

  • Hoare交换法（以pivot中点为例）
    减少了交换次数，效率更高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename T>
void QuickSort(vector<T> &vec, int left, int right) { 
// 1 
 T pivot = vec[(left + right) / 2];
// 2
 int i = left;
 int j = right;
 while (i <= j) {
     while (vec[i] < pivot) i++; // 从左找到一个>=pivot的元素
     while (vec[j] > pivot) j--; // 从右找到一个<=pivot的元素
     if (i <= j) // 交换两者位置
         swap(vec[i++], vec[j--]);
 }
 // 3
 if (left < j)  QuickSort(vec, left, j);
 if (i < right) QuickSort(vec, i, right);
}

复杂度

快排存在一定的随机性，主要来源于中点值的选择，

  • 最好情况O(NlogN)： 中点能平衡左右子树元素个数（选取的中点接近实际中点），那么属于最好情况
  • 最差情况O($N^2$)： 中点划分出的左右子树元素非常不平衡，如刚好选择了最大值或者最小值。会导致随着深度增加，元素规模只会逐个减少。
    • 如果每次选取端点为中点，那么对于完全逆序的情况，就是最差情况。
    • 选用随机基准法可以降低最差情况的概率
  • 平均O(NlogN)

*优化

  • 大规模下针对pivot选择做优化
    • 比如三位取中法， 从 数组左端，中断，右端选取一个中间大小的值，来提升中点能平衡左右个数的概率
  • 小规模下换其他算法
    • 因为递归调用和分割开销较大，可用插入排序代替
  • 3-way 特殊场景优化 相同的值做合并，每次划分，分成三个集合， 小于中点的集合，等于中点的集合，大于中点的集合
    • 如对于1 4 6 6 7 6 7 6 8 6 数组， 如果选取最右的6为中点，那么一轮划分后为 1 4 和 6 6 6 6 6 和 7 8 7
  • 双轴心快排 DualPivotQuicksort
    • Java Arrays.sort的标准实现java.util.DualPivotQuicksort
    • 个人认为是泛化了相同的值做合并，并结合小规模换插入排序
    • 大规模下每次设置两个轴点，分成3块 ，小规模下做插入排序，
    • 有兴趣可以阅读源码。
  • 多线程下的快排优化
    • TODO

我目前理解不够，以后有时间单独开一篇文章来讲快排各种优化与适用场景的理论和测试对比。

堆排序 Heap Sort

借助堆不断输出堆顶元素来实现排序

堆结构 （优先队列）

堆是一棵完全二叉树，要求树根就是所有元素中的最值。以大根堆为例，要求对于任意节点，其值 ≤ 左子树的值和右子树的值，即任意节点是其所在子树的最值。如下图：

常以树状数组存储，若数组索引以1开始,则对应要求可以书写为 a[i] >= a[i * 2], a[i] >= a[i*2]。如下图：

结构定义

以下 *2 /2操作建议用位移操作加速，在这里为了方便理解就不用位移操作取代了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<typename Item>
class MaxHeap{
private:
    Item *data;
    int count;
    int capacity;
    void shiftDown(int k);
    void shiftUp(int k);
public:
    MaxHeap(int capacity){
        data = new Item[capacity+1]; count = 0;this->capacity = capacity;
    }
    ~MaxHeap(){
        delete[] data;
    }
    MaxHeap(Item arr[], int n);

    void insert(Item item);
    Item extract();

    // 其他有关于获取顶端、获取count操作就不列举了
}

添加元素 O(logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void MaxHeap::insert(Item item){
    assert( count + 1 <= capacity );
    data[++count] = item;
    //通过shiftup保持堆的定义
    shiftUp(count);
}

//将位置k的元素尝试向根移动，不断替换比自己小的父亲节点
void MaxHeap::shiftUp(int k){
    while( k > 1 && data[k/2] < data[k] ){
        swap( data[k/2], data[k] );
        //交换过之后考虑当前节点，就是上次节点交换后的位置
        k /= 2;
    }
}

弹出顶端元素 O(logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Item MaxHeap::  extract(){
    assert( count > 0 );
    Item ret = data[1];

    //最后一个元素和第一个元素进行互换
    swap( data[1] , data[count] );
    count --;
    shiftDown(1);

    return ret;
}

// 从根向下不断替换比自己大的 且 最大的子节点
void shiftDown(int k) {
    //是否有左孩子存在孩子的判定
    while( 2*k <= count ){
        int j = 2*k; // 在此轮循环中,data[k]和data[j]交换位置
        //有右孩子并且右孩子大于左孩子
        if( j+1 <= count && data[j+1] > data[j] )
            //因为右孩子更大，所以将j更新为j+1
            j ++;
        // data[j] 是 data[2*k]和data[2*k+1]中的最大值

        if( data[k] >= data[j] ) break;
        swap( data[k] , data[j] );
        //新的变到了j的位置
        k = j;
    }
}

初始化 O(n)

对于所有非叶子节点做shiftDown

1
2
3
4
5
6
7
8
9
10
11
MaxHeap::MaxHeap(Item arr[], int n){
       data = new Item[n+1];
       capacity = n;

       for( int i = 0 ; i < n ; i ++ )
           data[i+1] = arr[i]; //下标从1开始
       count = n;

       for( int i = count/2 ; i >= 1 ; i -- )
           shiftDown(i);
   }
  • 误区： 不要以为N/2次shiftDown复杂度就是O(NlogN)，因为不同层的运算次数不一样，可以做如下证明
  • 复杂度证明：总高度为$h=logN$，第x层元素的计算量为$2^x * (h-x)$
    $S = 2^{h-1} × 1 + 2^{h-2} × 2 + …… + 1 × (h-1) = 2^h × 1 - h +1 = N -logN +1 = O(N)$

如何排序

就是初步初始化后，然后不断extract。第i次extract的数就是第i大的数，就完成了排序。

其实堆常见的不是用在排序，更多是用在动态维护最值的场合，作为优先队列，比如多个有序数列合并(多路归并)、dijstra的堆优化。

复杂度

  • 最好、最差、平均： O(NlogN) 即与快排相比，堆排没有最好最坏情况，每个情况都差不多。

  • 为什么一般比快排慢： 几乎没有最好情况。在堆排序的时候，每次extract总是将堆顶元素移除，然后将最后的元素放到堆顶，再让其自我调整。这两个元素往往差距很大，所以每轮的调整次数几乎每次都就近于高度。

归并排序 Merge Sort

这个思路是最简单的，是将排序分而治之的最直观算法，就是每次划分时保证左右子树个数接近甚至相等。 常用的 2 路归并排序假设初始序列有 n 个元素，可以看成是 n 个长度为 1 的子序列，进行两两归并，可以得到 n / 2 个长度为 2 或 1 的子序列；再两两归并，直到得到一个长度为 n 的有序序列为止。

实现

以下是便于理解的递归版本实现，每次将当前数组拆成两等分, 每一等分自己先完成排序，然后再通过merge操作将两个有序子序列成一个大的有序序列。
(在下面的代码中，end是无效索引，最后一个元素是A[end-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void merge(vector<int>& A, int start, int mid, int end)
{
    int n1 = (mid - start);
    int n2 = (end - mid);
    int L[n1], R[n2];

    memcpy(L, &A[start], sizeof(int) * n1);
    memcpy(R, &A[mid], sizeof(int) * n2);
    
    int i = 0, j = 0;
    for (int k = start; k < end; k++) {
        if (j >= n2 || (i < n1 && L[i] <= R[j]))
            A[k] = L[i++];
        else
            A[k] = R[j++];
    }
}

void mergesort(vector<int>& A, int start, int end)
{
    if (start < end-1) {
        int mid = (start + end) / 2;
        mergesort(A, start, mid);
        mergesort(A, mid, end);
        merge(A, start, mid, end);
    }
    else
        return 0;
}

复杂度

  • 最好、最差、平均： O(NlogN)
  • 为什么一般比快排慢：需要额外的空间做数组复制，额外空间复杂度为O(N)

归并排序相关问题

非比较排序

不基于比较，与其说像排序，更不如说像统计。都是拿空间换时间的策略，只适合元素范围较小的场合。

计数排序 Counting Sort

统计每个元素出现个数，然后按元素从小到大遍历输出。
复杂度O(N+M), M是元素大小的范围(MAX-MIN)

桶排序 Bucket Sort

是计数排序的变种，把计数排序中相邻的m个”小桶”放到一个”大桶”中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。

  • 平均时间复杂度为线性的O(N+C), C为桶内快排的时间复杂度。
  • 如果刚好所有数据到一个桶里了，就是最差情况

基数排序 Radix Sort

可以理解多级桶排序，基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
过程：

  1. 取得数组中的最大数，并取得位数；
  2. arr为原始数组，从最低位开始取每个位组成radix数组；
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

演示：

稳定性

  • 定义： 待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

  • 稳定算法：
    基数（桶）、冒泡、插入、归并

  • 不稳定算法
    快速、堆、希尔、选择

证明基于比较的排序复杂度不可能低于O(NlogN)

所有基于比较的排序算法，都可以抽象成一个决策数模型，为一个完全二叉树。

N个数的原始排列情况一共$n!$种情况，那么这棵能区分这$n!$种情况的决策树深度
$$ h \geq log(n!)$$
由于斯特林公式
$$n! \approx \sqrt{2\pi n}, \left(\frac{n}{e}\right)^{n} $$
最后得出
$$h \geq log(\sqrt{2\pi n}, \left(\frac{n}{e}\right)^{n} ) = log(\sqrt{2\pi n}) + nlog(n/e) = O(nlogn)$$

最后小小的总结

排序算法空间复杂度(平均)时间复杂度（平均）时间复杂度（最坏）时间复杂度（最好）是否稳定
冒泡$O(1)$$O(n^2)$$O(n^2)$$O(n)$稳定
选择$O(1)$$O(n^2)$$O(n^2)$$O(n^2)$不稳定
(直接)插入$O(1)$$O(n^2)$$O(n^2)$$O(n^2)$稳定
希尔$O(1)$$O(n^{1.3})$$O(n^2)$$O(n)$不稳定
快速$O(logn)$$O(nlogn)$$O(n^2)$$O(nlogn)$不稳定
归并$O(n)$$O(nlogn)$$O(nlogn)$$O(nlogn)$稳定
堆$O(1)$$O(nlogn)$$O(nlogn)$$O(nlogn)$不稳定
计数$O(n+k)$$O(n+k)$$O(n+k)$$O(n+k)$稳定
桶$O(n+k)$$O(n+k)$$O(n^2)$$O(n)$稳定
基数$O(n+k)$$O(n*k)$$O(n*k)$$O(n*k)$稳定

对于非比较排序，空间复杂度存在争议，因为有些排序在桶内会额外存储原值，有些不存。该表中空间复杂度是针对存原值的。

Reference

C++ Implementations of Quicksort Methods for Sorting Arrays with Lots of Duplicates
面试10大排序算法总结
九种排序算法的可视化及比较
图解排序算法(二)之希尔排序
快速排序的几种常见实现及其性能对比 - 点滴算法
算法与数据结构（四）堆排序：优先队列实现 - 腾讯云社区
十大经典排序算法（动图演示）