内部排序算法详解

本文首发于 LOGI'S BLOG，由作者转载。

内部排序是指待排序列完全位于内存中的排序过程，适合内存充足，能够一次性加载整个序列的情况，与此对应的还有外部排序。本文将详细介绍几种经典非线性内部排序算法的原理和实现，并分析各自的稳定性和时空性能。

排序算法的稳定性

采用何种排序算法，除了考虑数据规模和时空复杂度，特定场景下，稳定性也常常成为重要指标。我们称，满足以下特征的排序算法具有稳定性：使用某排序算法对待排序列排序，假设序列中有两个元素 e1 和 e2，e1.key = e2.key 且 e1 位于 e2 之前，使用该排序算法后，e1 仍处于 e2 之前。

既然 e1.key = e2.key，那么最终谁在前面又有什么影响呢？大多数情况下确实没有影响，但如果对复杂对象的多个属性排序，且下一次排序要保持上一次的某些局部相邻顺序，就要使用稳定的排序算法。例如要对商品对象按销量排序，如果销量相同就按价格排序。我们可以首先按价格排序，随后使用稳定的算法对销量排序。当然你也可以先按销量排序，随后遍历序列，在每个销量相同的区间里分别按价格排序，不过这样实现相对复杂，也不适合价格本身有序的情况。

快速排序

之所以首先介绍快速排序，一来因为它的平均时间复杂度为 O(nlogn)，空间复杂度为 O(logn)，在所有内部排序算法中综合性能最优，二来其主要思想是上一节介绍的分治与递归，可当作递归的应用讲解。

基本思想

回顾能用递归解决的问题必须满足的三个条件：首先，原问题能够分解为几个规模较小的子问题。其次，原问题和子问题是同一问题。第三，存在终止条件。具体到排序，试想这样的操作：选定待排序列中任一元素作为分界点，将小于分界点的元素都放到其左边，大于分界点的元素都放到其右边，问题便转换为对分界点两侧的序列排序。分好类后，对于每个子序列，仍可使用上面的方法排序，即从原问题到子问题，规模变小，解决方法相同。当子序列仅有一个元素时，无需排序，这便是终止条件。可见，排序问题可以用递归解决。

现在寻找递推公式，假如要对数组下标从 p 到 r 之间的元素由小到大排序，选择在此之间的任意元素作为分界点 pivot，遍历待排序列，将小于 pivot 的元素放到其左边，大于 pivot 的元素放到其右边，下面是一个示例

                  pivot
                    ↓
[8][10][2][3][6][1][5]
 p                  r
        分 |
        区 ↓
[2][3][1][5][6][8][10]
 p        q         r

记对下标从 p 到 r 之间的序列排序的过程为 f(p, r)，q 是分区结束后 pivot 的数组下标，则对下标从 p 到 q-1 之间序列排序的过程为 f(p, q-1)，对下标从 q+1 到 r 之间序列排序的过程为 f(q+1, r)，要使整个序列有序，只要对两个子序列分别排序即可，所以 f(p, r) = f(p, q-1) and f(q+1, r)。

当子序列仅有一个元素，即 p >= r 时，排序结束，加上 > 的原因将在后面说明。下面是递归函数的实现代码

// 分区函数
int partition(int[] a, int p, int r) {
    // 选择任意元素作为分区点 pivot，对 a 分区，
    //+ 使 pivot 左边都小于它，右边都大于它，
    //+ 最后返回分区结束后 pivot 的下标
    // ...
}

void quickSort(int[] a, int p, int r) {
    if (p >= r) return;
    int q = partition(a, p, r);
    quickSort(a, p, q-1);
    quickSort(a, q+1, r);
}

现在考虑如何高效实现 partition 函数，基本想法是开辟两个新数组 b 和 c，将小于 pivot 的元素拷贝到 b，大于 pivot 的元素拷贝到 c，最后再将 b，c 拷贝回 a。但这样实现的空间复杂度是 O(2n)，能否将其降到 O(1) 呢？考虑这样的做法：选定最后一个元素 a[r] 为 pivot，用 i 将 a[p, r-1] 分成两部分，记 a[p, i-1] 为 已处理区间，a[i, r-1] 为未处理区间。起初 i=p，遍历未处理区间，每次从中取一个元素 a[j]，若小于 pivot，则将其加入已处理区间末尾，即 a[i] 位置，此时已处理区间增加一个元素，i++。最终，i 前面都比 pivot 大，将 pivot 放到 i 位置，返回 i。下面是完整示例

p           r
ij         pivot
6  11 3  9  8    6<8，将 6 加入已处理序列，i 后移。继续遍历未处理序列，j 后移

   ij
6  11 3  9  8    11>8，继续遍历未处理序列，j 后移

    i j
6  11 3  9  8    3<8，将 3 加入已处理序列，i 后移。继续遍历未处理序列，j 后移

       i  j
6  3  11  9  8   9>8，未处理序列遍历完毕

      i  j
6  3  8  9  11   交换 8 和 11，将 pivot 移动到已处理序列末尾

我们知道往数组插入元素的平均复杂度是 O(n)，那么整个 partition 函数的时间复杂度将是 O(n^2)，显然是可不取的。在操作数组的几个技巧中我们提到，如果仅将数组当作数据集合使用，无需考虑元素顺序，那么将元素插入到第 k 个位置的操作可简化为：将第 k 个位置的元素插入到数组尾，将新元素放到第 k 个位置上，不做数据搬移，时间复杂度为 O(1)。

此处，因为 a[i] 和 a[j] 都处于未处理序列中，而未处理序列的顺序我们并不关心，所以要将 a[j] 插入到 a[i] 的位置上，只需将两者交换，这样，插入便成为 O(1) 操作，整个 partition 函数的时间复杂度就是 O(n)。因为没有使用额外空间，空间复杂度是 O(1)。下面是 partition 的实现代码

void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

int partition(int[] a, int p, int r) {
    // 选取最后一个元素作为分界点
    int pivot = a[r];
    // 起初，整个序列都处于未处理区间
    int i = p;
    // 遍历未处理区间
    for( int j=i; j<r; j++) {
        // 如果元素比分界点小，则将其放到已处理序列末尾
        if (a[j] < pivot)
            // 已处理序列增加一个元素
            swap(a, i++, j);
    }
    // a[i] 之前都小于 pivot，将 pivot 放到 i 位置即可
    swap(a, i, r);
    return i;
}

考虑序列 1，2，3，4，5，第一次调用 partition 后将返回 4，所以会执行 quickSort(0，3)，quickSort(5, 4)，此时 5 > 4，这就是递归终止条件写成 p >= r 的原因。

稳定性

考虑序列 6，8，7，6，3，5，在 3 之前的元素都大于 5，而 3<5，所以第一个 6 要与 3 交换，这样序列中两个 6 的顺序就发生了变化，由此可见，快速排序是 不稳定 的排序算法。

性能分析

最好时间复杂度

快排所需时间等于对数组进行划分的时间加上两次递归调用的时间。假如每次 partition 都能把数组分成大小近似相等的两个子区间，那么递归的层数将到达最小，所花时间最少。记对 n 个元素进行快速排序的时间为 T(n)，那么对每个子区间排序的时间就是 T(n/2)，有 T(n) = n + 2 * T(n/2)，其中 n 为划分所花时间。当 n = 1 时无需排序，即 T(1) = C。假如整个过程进行了 k 次递归，有
$\begin{equation} \begin{aligned} T(n) &= n + 2 * T(\frac{n}{2})\\ &= 2n + 4 * T(\frac{n}{4})\\ &= 3n + 8 * T(\frac{n}{8})\\ &...\\ &= kn + 2^{k} * T(\frac{n}{2^{k}}) \end{aligned} \end{equation}$
当 n/2^k = 1，即 k = logn 时，T(n) = nlogn + Cn。所以快速排序的最好时间复杂度是 O(nlogn)。

最坏时间复杂度

如果待排序列初始状态是逆序，每次递归前半部分没有元素，后半部分元素个数为整个序列长度减 1，所以总共要进行 n 层递归，每层递归中，划分操作的时间复杂度是 O(n)，所以最坏时间复杂度是 O(n^2)。

平均时间复杂度

记对 n 个数进行划分后，k-1 个数被划分到左边，k 可能是 1-n 之间的任意数字，且每种可能概率相等，都是 1/n。所以对 n 个数进行快速排序，其平均时间的递推公式如下，其中 Cn 是划分所用时间：
$T(n)=Cn+\frac{1}{n}\sum_{k=1}^n[T(k-1)+T(n-k)]$
记 S(n-1) = T(0) + T(1) + ... + T(n-1)，有
$T(n)=Cn+\frac{2}{n}S(n-1)$
移项得
$S(n-1)=\frac{n}{2}[T(n)-Cn]$

$S(n-2)=\frac{n-1}{2}[T(n-1)-C(n-1)]$

因为 T(0)=T(1)=1，所以
$T(n-1)=S(n-1)-S(n-2)=\frac{n}{2}[T(n)-Cn)]-\frac{n-1}{2}[T(n-1)-C(n-1)]$
等号两边同时乘 2 并移项整理得
$nT(n)=(n+1)T(n-1)+2Cn-C$
为了简化计算，去除最后的非决定项 -C，两边同时除以 n(n+1) 得
$\frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{2C}{n+1}$
现在进行叠缩
$\frac{T(n-1)}{n}=\frac{T(n-2)}{n-1}+\frac{2C}{n}\\ \frac{T(n-2)}{n-1}=\frac{T(n-3)}{n-2}+\frac{2C}{n-1}\\ ...\\ \frac{T(2)}{3}=\frac{T(1)}{2}+\frac{2C}{3}$
将以上叠缩式相加并约分整理得
$\frac{T(n)}{n+1}=\frac{T(1)}{2}+2C\sum_{i=3}^{n+1}\frac{1}{i}$
上式的最后一项是调和级数的部分和，两边同时乘以 n+1 得
$T(n)=2C(n+1)[ln(n+1)+r-3]+\frac{n+1}{2}，r 为欧拉-马歇罗尼常数$
所以，快速排序的平均时间复杂度是 O(nlogn)。

空间复杂度

最坏情况下，快速排序要进行 n 层递归，空间复杂度 O(n)，最好和平均情况下要进行 logn 层递归，空间复杂度 O(logn)。

快速排序的优化

针对快排的优化主要从四个方面入手。第一，固定位置选取 pivot 容易导致分割不均，通常采用三数取中法。第二，对于重复元素过多的序列，可将所有与 pivot 相等的元素移到 pivot 两边，下次递归时忽略这些元素。第三，元素较少时采用插入排序。第四，将第二个递归改为循环，即尾递归优化，通常编译器会自动进行。

应用：寻找第 K 大数

有很多种做法，首先是直接排序，时间复杂度为 O(nlogn)。其次是循环 K 次，每次排除当前数组的最小值，时间复杂度 O(Kn)。更好的做法是利用快排的分区思想，例如数组 a[p,r]，每次选取 a[r] 作为 pivot 将数组分成三个区 a[p, pivot-1]，a[pivot] 和 a[pivot+1,r]。如果 pivot+1 = K，则 a[pivot] 就是第 K 大数。如果 pivot+1 < K，则结果在 a[pivot+1,r] 中，反之结果在 a[p, pivot-1] 中。假如 pivot 每次都能将数组平分，那么整个过程要遍历的元素个数为
$\begin{equation} \begin{aligned} T(n)&=n+\frac{n}{2}+\frac{n}{4}+...+\frac{n}{2^{k}}+1\\ &=n(1+\frac{1}{2}+\frac{1}{4}+...+\frac{1}{2^k})+1\\ &=n\frac{1-\frac{1}{2^{k+1}}}{1-\frac{1}{2}}+1\\ &=2n-\frac{n}{2^k}+1,\ 2^{k+1}=n\\ &=2n-1 \end{aligned} \end{equation}$
所以时间复杂度为 O(n)，下面是示例代码

int kTh(int[] a, int p, int r, int k) {
    int q = partition(a, p, r);
    int cTh; // 保存 q 位置是第几大数
    while ((cTh = q + 1 - p) != k) {
        if (cTh > k) {
            q = partition(a, p, q - 1);
        } else {
            q = partition(a, q + 1, r);
        }
    }
    return a[q];
}

递归实现更容易理解。

int kTh(int[] a, int p, int r, int k) {
    int q = partition(a, p, r);
    int cTh = q + 1 - p;

    if (cTh == k)
        return a[q];
    else if (cTh > k)
        return kTh(a, p, q - 1, k);
    else
        return kTh(a, q + 1, r, k - cTh);
}

归并排序

归并排序与快速排序一样，也利用了分治思想，并且其最好最坏和平均时间复杂度都是 O(nlogn)，除此之外它还是稳定的排序算法，唯一缺点是空间复杂度为 O(n)。

基本思想

将待排序列从中间分成两部分，对它们分别排序，最后将排好序的两部分合并。下面是一个示例：

---                11 8  3  9  7  1  2  5
 ↓                ↙                      ↘
           11 8  3  9                  7  1  2  5
分         ↙         ↘                ↙         ↘
         11 8        3  9             7  1        2  5
 ↑      ↙   ↘      ↙   ↘         ↙   ↘      ↙   ↘  
---    11    8       3    9        7      1      2     5
 ↓      ↘   ↙       ↘   ↙        ↘   ↙      ↘   ↙
        8  11         3  9            1  7        2  5
合        ↘          ↙                 ↘        ↙
          3  8  9  11                    1  2  5  7
 ↑                 ↘                     ↙
---                 1  2  3  5  7  8  9  11

如上图所示，对于每个子序列我们仍然可以继续分割，直到子序列只有一个元素时，它肯定是有序的，随后将有序子序列逐层合并就能使整个序列有序。记为 p，r 间序列排序的过程为 mergeSort(p,r)，以 p，r 中点 q 将序列分成前后两部分，则对两部分分别排序的过程为 mergeSort(p,q) 及 mergeSort(q+1,r)，合并数组 a,b 的过程为 merge(a,b)，则有以下递推公式

mergeSort(p,r) = merge(mergeSort(p,q), mergeSort(q+1,r)), q=(p+r)/2

递归终止条件为 p >= r，大于号在序列仅有 2 个元素时取到，不妨令 p=0，r=1，则 q = (p+r)/2 = 0，此时会执行 mergeSort(0, 0) 和 mergeSort(1, 0)，满足 p>=r。下面是实现代码

void mergeSort(int[] a, int p, int r) {
    if (p >= r) return;
    int q = (p+r)/2;
    mergeSort(a, p, q);
    mergeSort(a, q+1, r);
    merge(a, p, r, q);
}

上述代码中 merge 函数的作用是合并原始序列 a[p,r] 的前后两部分，具体做法是开辟一个与待合并序列大小相等的新数组 tmp，随后设定两个指针 i 和 j 分别指向两个待合并序列的起始位置 p 和 q+1，比较 a[i] 和 a[j]，将较小者放入 tmp 末尾，同时相应指针后移。如果某个指针走至所在部分末尾，则将另一指针所在部分剩余元素全部插入 tmp 末尾，最后将 tmp 拷贝回数组 a。下面是实现代码

void merge(int[] a, int p, int r, int q) {
    int[] tmp = new int[r-p+1];
    int i = p;
    int j = q+1;
    int k = 0;
    
    while (i<=q && j<=r)
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    
    while (i <= q)
        tmp[k++] = a[i++];
    
    while (j <= r)
        tmp[k++] = a[j++];
    
    for (k=0,; k<r-p+1; k++)
        a[p+k] = tmp[k];
}

稳定性

容易看出，归并排序的稳定性依赖于合并函数 merge，具体来说是函数的第 9 行 if (a[i] <= a[j])。上述代码实现的是从小到大排序，其中 a[i] 位于前半部分，a[j] 位于后半部分。根据语义，当 a[i]=a[j] 时，a[i] 会先于 a[j] 进入数组，这就决定了 a[i] 最终仍会位于 a[j] 之前，所以归并排序是 稳定 的排序算法。

性能分析

时间复杂度

记对含 n 个元素的序列排序所需时间为 T(n)，由于每次都是平分序列，所以 T(n) = 2*T(n/2) + n，其中 n 为合并所需时间，有以下递推公式
$\begin{equation} \begin{aligned} T(n) &=2*T(\frac{n}{2})+n\\ &=2*2*T(\frac{n}{4})+2n\\ &...\\ &=2^{k}*T(\frac{n}{2^{k}})+kn\\ \end{aligned} \end{equation}$
假设整个排序过程需要 k 层递归，由于递归的终止条件是 T(1) = 1，可令 n/2^k = 1，即 k=logn，则
$T(n)=n+n*log_2n$
所以，归并排序的时间复杂度是 O(nlogn)。需要注意的是，由于每次都是平分序列，无论初始状态如何，归并的时间都是相同的，即最好、最坏和平均时间复杂度都是 O(nlogn)。

空间复杂度

归并排序中的 merge 函数需要 O(n) 的额外空间，虽然整个排序过程要进行 logn 层递归，但上层 merge 执行时，下层 merge 已经将空间释放，又 O(logn) < O(n)，所以归并排序的空间复杂度是 O(n)。

插入排序

基本思想

往有序数组插入新元素，要求插入后数组仍然有序，做法是遍历数组，找到合适的位置后将后面所有元素搬移，最后将新元素插入到那个位置，插入排序便利用了该思想。

和快速排序的 partition 函数一样，插入排序也将数组分为 已排序 和 未排序 两个区间，起初已排序区间只有一个元素，即数组首元素。每次取未排序区间的第一个元素，在已排序区间中找到合适位置并插入，重复这个过程，直到未排序区间为空，算法结束。下面是一个示例

     sorted | unsorted
          4 | 5 6 1 3 2
        4 5 | 6 1 3 2
      4 5 6 | 1 3 2
    1 4 5 6 | 3 2
  1 3 4 5 6 | 2
1 2 3 4 5 6 |

下面是实现代码

void insertionSort(int[] a) {
    if (a.length<2) return;
    
    for (int i = 1; i < a.length; i++) {
        // 当前元素比已处理序列最大值都大，直接放末尾
        if (a[i] >= a[i-1]) continue;
        
        //保持未处理序列首元素，避免覆盖
        int t = a[i];
        
        // 记录插入位置，i 是未处理序列头，i-1 是已处理序列尾
        int j = i-1;
        
        // 逆序遍历已处理序列，寻找合适插入位置，并将之后的元素后移
        for (; j>=0 && a[j]>t; j--)
                a[j+1] = a[j];
        
        // 插入到合适位置
        a[j+1] = t;
    }
}

稳定性

上述代码内部 for 循环的终止条件 a[j] > t 决定，当元素相等时，后出现的元素不会插入到前面，所以插入排序是 稳定 的排序算法。

性能分析

最好时间复杂度

当元素本身有序且为正序时，插入排序无须移动元素，时间复杂度为 O(n)。

最坏时间复杂度

当元素逆序时，每次插入都要移动已处理序列的所有元素，时间复杂度为 O(n^2)。

平均时间复杂度

当 i<j 时，若 a[i]<=a[j]，则称 a[i] 与 a[j] 为一组有序元素对，有序度是数组中有序元素对的个数。逆序度的定义与有序度相反。对于完全有序的数组，称它的有序度为满有序度。对于含 n 个元素的数组，其满有序度为
$\begin{equation} \begin{aligned} FullOrderDegree &=(n-1) + (n-2) + ... + 1\\ &=\frac{n(n-1)}{2} \end{aligned} \end{equation}$
满有序度=逆序度+有序度，排序就是增加有序度，减少逆序度的过程。插入排序包含两个操作，比较和移动，对于给定的初始序列，每次遍历已处理序列时，只有逆序才需要移动，每移动一个元素，逆序度都减 1，所以插入排序的移动次数等于初始序列的逆序度。

另一方面，插入排序本质是 n 次数组插入，数组插入的平均复杂度为 O(n)，所以插入排序的平均时间复杂度就为 O(n^2)。

空间复杂度

算法使用了常数级的额外空间，所以最好最坏和平均空间复杂度都为 O(1)。

插入排序的优化

折半插入排序

因为已处理序列是有序的，因此可使用折半查找的方法寻找插入位置，这样可将比较次数降低到 O(nlogn)。下面是示例代码

void insertSort(int[] a) {
    if (a.length<2) return;
    // 遍历未处理序列
    for (int i=1; i<a.length; i++) {
        // 未处理序列首元素大于已处理序列尾元素，直接插入到末尾
        if (a[i] >= a[i-1]) continue;
        
        // 记录未处理序列首元素，避免移动元素覆盖
        int t = a[i];
        
        //  在已处理序列中通过二分搜索，找到最后一个大于 t 的位置
        //+ 因 low>high 才会退出循环, 所以退出前执行了 high = mid-1，
        //+ 这意味着 low=mid，a[mid]>t，所以 low 是最后一个大于 t 的位置
        int low = 0;
        int high = i-1;
        while (low <= high) {
            int mid = (low+high)/2;
            if (a[mid] > t)
                high = mid-1;
            else
                low = mid + 1;
        }
        
        // 逆序遍历已处理序列，移动元素
        for(int j=i-1; j>=low; j--)
            a[j+1] = a[j];
        
        // 插入到合适位置
        a[low] = t;
    }
}

希尔排序

直接插入排序的移动次数等于初始序列的逆序度，如果数据规模较小且初始序列基本有序，比较和移动次数就会显著降低。基于以上两点 D.L.Shell 于 1959 年发明了希尔排序，其基本思想是：把记录下标按一定增量分组，对每组使用直接插入排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个文件恰被分成一组，再进行一次插入排序，整个序列便达到有序。

简单插入排序很循规蹈矩，不管数组分布是怎么样的，都一步一步地对元素进行比较，移动，插入。比如 [ 5, 4, 3, 2, 1, 0 ] 这种倒序序列，数组末端的 0 要回到首位很是费劲，比较和移动均需 n-1 次。希尔排序采用跳跃式分组策略，通过某个增量将数组元素划分为若干组，分组进行插入排序。处理完所有组后，减小增量，继续按组进行插入排序，直至增量为 1。通过这种策略使得整个数组在初始阶段达到宏观基本有序，到增量为1时，只需微调即可。

目前尚未求得一个最好的增量序列，希尔的做法是 d1=n/2, d(i+1)=⌊di/2⌋，且最后一个增量为 1。在理解希尔排序时，我们倾向于逐组处理，但在代码实现中，不用处理完一组再回去处理下一组（这样还得加个 for 循环去处理分组）。比如 [ 5, 4, 3, 2, 1, 0 ] ，首次增量设 d1=length/2=3，将序列分成 3 组 [ 5, 2 ] [ 4, 1 ] [ 3, 0 ]，实现时不用循环按组处理，而是从第 d1 个元素开始逐个遍历，实现跨组处理。以下是示例代码

void shellSort(int[] a, int n) {
    if (n < 2) return;
    
    // 间距逐步减小，每组元素逐步增多，分组数逐步减少
    for (int dk=n/2; dk>=1; dk/=2) {
        //  逐个遍历，实现跨组处理
        //+ 随着 i++，dk 分别是第一组，第二组，... ，第 dk 组未处理序列的第  一  个元素，
        //+                   第一组，第二组，... ，第 dk 组未处理序列的第  二  个元素，
        //+ ...
        //+                   第一组，第二组，... ，第 dk 组未处理序列的第 n/dk 个元素。
        for (int i=dk; i<a.length; i++) {
            // 如果未处理序列开头比已处理序列最大值还大，直接放末尾
            if (a[i] >= a[i-dk]) continue;
            
            // 记录未处理组开头，避免覆盖
            int t = a[i];
            
            // 记录插入位置，i-dk 是已处理序列最后一个元素
            int j = i-dk;
            
            // 遍历已处理序列，将大元素后移
            for(; j>=0 && t<a[j]; j-=dk)
                a[j+dk] = a[j];
            
            // 插入到合适位置
            a[j+dk] = t;
        }
    }
}

此外除了一次性移动所有元素，也可采用将待插入元素逐个与大于它的元素交换的方法，以下是示例代码

void shellSort(int[] a, int n) {
    if (n < 2) return;
    
    for (int dk=n/2; dk>0; dk/=2) {
        for (int i=dk; i<a.length; i++) {
            if (a[i] >= a[i-dk]) continue;
            for (int j=i; j-dk>=0 && a[j]<a[j-dk]; j-=dk)
                swap(a, j, j-dk);
        }
    }
}

当相等元素被划分到不同组时，可能会改变它们的相对次序，所以希尔排序是 不稳定 的排序算法。下面的示例一目了然

3  2  2* 1  0  dk=5/2=2
^     ^     ^
0  1  2* 2  3
^     ^     ^

0  1  2* 2  3  dk=2/2=1

希尔排序的空间复杂度为 O(1)，它的时间复杂度依赖于增量序列函数，这涉及到数学上尚未解决的难题，所以不便准确分析，当 n 在某个特定范围时，其时间复杂度约为 O(n^1.3)，最坏情况下时间复杂度为 O(n^2)。希尔排序是冲破 O(n^2) 的第一批算法之一。

选择排序

基本思想

与插入排序类似，选择排序也将数组分为已排序和未排序区间，不同的是，选择排序每次从未排序区间选择最小元素后缀至已排序区间。因为并不关心未排序区间第一个元素 p 和最小元素 min 的顺序，并且 p 将在下一步进入已排序区间，所以后缀 min 的操作可以转换为交换 p 和 min，下面是一个示例

     sorted | unsorted
            | 4 5 6 3 2 1 swap 4 and 1
          1 | 5 6 3 2 4   swap 5 and 2
        1 2 | 6 3 5 4     swap 6 and 3
      1 2 3 | 6 5 4       swap 6 and 4
    1 2 3 4 | 5 6         swap 5 and 5
  1 2 3 4 5 | 6           swap 6 and 6
1 2 3 4 5 6 |

下面是实现代码

int selectionSort(int[] a) {
    for (int i=0; i<a.length; i++) {
        int minIndex = i;
        for(int j=i+1; j<a.length; j++)
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        swap(a, i, minIndex);
    }
}

稳定性

考虑序列 5，6，5，2，9，第一次找到的最小元素是 2，要将其与第一个 5 交换，这样就改变了两个 5 的顺序，所以选择排序 不具有稳定性。

性能分析

时间复杂度

无论原始序列有序性如何，选择排序都要进行 n 次寻找最小值的操作，而寻找最小值的时间复杂度是 O(n)，所以选择排序的最好最坏和平均时间复杂度都是 O(n^2)。

空间复杂度

算法使用了常数级空间，所以空间复杂度为 O(1)。

冒泡排序

基本思想

同样将数组分为已就绪和未就绪区间，初始状态整个数组都未就绪。遍历未就绪区间，比较相邻元素，若不满足大小关系则交换，一次遍历会至少让一个元素移动到它应该在的位置，重复 n-1 次就完成了排序工作。下面是一次冒泡过程

从小到大排序，if(a[j] > a[j+1]) 交换
4 5 6 3 2 1 , 4<5 不交换
j
4 5 6 3 2 1 , 5<6 不交换
  j
4 5 6 3 2 1 , 6>3   交换
    j
4 5 3 6 2 1 , 6>2   交换
      j
4 5 3 2 6 1 , 6>1   交换，结束
        j
首次冒泡后，整个数组的最大值到达最终位置，下次冒泡，次大值将到达最终位置
还可以看出，若某次冒泡，如果未就绪序列有 m 个元素，则要进行 m-1 次比较

某些情况下，排序操作不需要 n-1 次冒泡，因为如果某次冒泡没有发生数据交换，说明未就绪序列相邻元素全部满足大小关系，即未就绪序列实际上已经就绪，可停止后续冒泡，下面是示例代码

void bubbleSort(int[] a) {
    for (int i=0; i<a.length-1; i++) {
        boolean sorted = true;
        for (int j=0; j<a.length-i-1; j++) {
            if(a[j]>a[j+1]) {
                swap(a, j, j+1);
                sorted = false;
            }
        }
        if(sorted) break;
    }
}

稳定性

冒泡排序只交换相邻元素，对于非相邻相等元素，最终会因逐个交换而相邻，因此只要保证相等元素不交换，就可保证排序的稳定性。换句话说，冒泡排序是 稳定 的排序算法。

性能分析

最好时间复杂度

当元素和待排顺序相同时，只需一次冒泡，所以最好时间复杂度为 O(n)。

最坏时间复杂度

当元素逆序是，要进行 n-1 次冒泡，所以最坏时间复杂度为 O(n^2)。

平均时间复杂度

冒泡排序的两个基本操作是比较和交换。每进行一次交换，序列的有序度就加 1，所以冒泡排序的交换次数等于原始序列的逆序度。

对于包含 n 个元素的数组，最坏情况逆序度为 n(n-1)/2，最好情况逆序度为 0，粗略取中间值 n(n-1)/4 作为平均逆序度，则冒泡排序的平均交换次数为 n(n-1)/4，比较次数显然大于交换次数，而最坏时间复杂度为 O(n2)，所以其平均时间复杂度为 O(n^2)。

空间复杂度

算法使用了常熟级额外空间，所以最好最坏和平均时间复杂度都是 O(1)。

堆排序

如果一棵二叉树的结点要么是叶子结点，要么该节点有两个子结点，那么这颗树就是满二叉树。完全二叉树是由满二叉树引申出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。也可以这样定义：设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大，第 h 层所有的结点都连续集中在最左边，这颗树就是完全二叉树。

堆 (Heap) 又被称为优先队列 (Priority Queue)。尽管名为优先队列，但它并不是队列。队列先进先出，而堆必须根据优先级取出元素。由完全二叉树 (Complete Binary Tree) 实现的堆称为二叉堆 (Binary Heap)。二叉堆是具有下列性质的完全二叉树：如果一颗完全二叉树每个节点的值都大于等于（小于等于）其左右孩子节点的值，则将这颗完全二叉树称为大顶堆或大根堆（小顶堆或小根堆）。堆的主要操作是添加最后一个节点和删除第一个节点，在插入或删除后，必须仍保持堆的性质: 1. 完全二叉树。2. 每个节点值都大于等于（小于等于）它的子节点。

插入新节点 new 时，将其放到最后一个节点之后，此时可能破坏堆的性质，要进行调整，具体操作为：将 new 与父节点比较，构建大根堆时，如果 new 节点比父节点大，那么交换两者。交换之后，继续与父节点比较，直到 new 节点不比父节点大，或者 new 节点成为根节点。下面是一次建立大根堆的过程

          53
      17      78
    09  45  65  87
    ↑
32

          53
      17      78
              ↑
    32  45  65  87
09

          53
      17      87
      ↑
    32  45  65  78
09

          53
          ↑
      45      87
    32  17  65  78
09

          87
      45      53
               ↑
    32  17  65  78
09

          87
      45      78
    32  17  65  53
09

堆只能删除根节点。根节点删除后，会得到两棵子树，需要基于它们重构堆：让最后一个节点 last 成为根构成新二叉树，再将 last 节点不断和子节点比较，构建大根堆时，如果 last 节点比两个子节点中大的那个小，则与该子节点交换。继续比较，直到 last 不小于任一子节点，或成为叶节点时，堆重构完成。堆排序（Heap Sort）便是利用堆设计的排序算法。

基本思想

堆排序是一种树形选择排序，其基本思想是：将待排数组构建成大根堆，不断删除堆顶（最大值）直到堆中仅含一个元素，排序完成。以下是示例代码

// 不使用 a[0]，len 为无序区（堆）元素个数
void heapSort(int[] a, int len) {
    // 仅含一个元素，无需排序
    if (len < 2) return;
    
    // 建立大根堆，堆顶 a[1] 是最大值
    buildMaxHeap(a, len);
    
    // 不断处理无序区（删除堆顶），直到仅含一个元素
    while (len > 1) {
        // 将最大值移到有序区，堆元素减一
        swap(a, 1, len--);
        
        // 从根开始往下调整，使之成为新堆
        adjustDown(a, 1, len);
    }
}

void buildMaxHeap(int[] a, int len) {
    //  len/2 是最大非叶节点（对应最后一颗子树）
    //+ 建堆过程就是从最大非叶节点向上遍历，一直到根，
    //+ 在此过程中，在每个非叶节点处向下调整，使对应子树满足堆的性质
    for (int i=len/2; i>0; i--)
        adjustDown(a, i, len);
}

// 将元素 k 向下调整，使子树成为堆，len 为堆中节点数
void adjustDown(int[] a, int k, int len) {
    // 保存当前非叶节点
    a[0] = a[k];
    
    // 沿较大子节点向下筛选，从左子节点(2k)开始
    for (int i=2*k; i<=len; i<<1) {
        // 若右子节点大于左子节点，则 i 移动到右子节点
        if (i < len && a[i]<a[i+1])
            i++;
        
        //  若当前非叶节点大于左右子树，则已经
        //+ 满足堆的性质，无需继续向下调整
        if (a[0] >= a[i])
            break;
        else {
            // 否则将左右子节点的较大者上移
            a[k] = a[i];
            
            // 非叶节点下移
            k = i;
        }
    }
    
    // 将当前非叶节点放到合适位置，即第一次大于等于其子节点的位置，或最后一个叶子节点
    a[k] = a[0];
}

向下调整也可用递归实现，每次递归处理一层。

void adjustDown(int[] a, int k, int len) {
    int i = 2 * k;
    if (i > len)
        return;
    if (i + 1 <= len && a[i] < a[i + 1])
        i++;
    if (a[0] >= a[i])
        return;
    swap(a, k, i);
    adjustDown(a, i, len);
}

稳定性

在进行筛选时，有可能把后面相等的元素调整到前面，所以堆排序是 不稳定 的排序算法。下面是一个演示示例

待排序列 
1  2  2*

建立大根堆
   2
1     2*

删除堆顶，已排序列为 2
   2*
1

删除堆顶，已排序列为 2* 2
   1

堆中仅剩一个元素，排序结束，最终序列为
1  2*  2

性能分析

时间复杂度

记树高为 h，则向下调整时间为 O(h)。建堆过程中每次向下调整时，大部分节点高度都较小，可证明建堆时间为 O(n)。如下是证明方法：假设完全二叉树有 n 个节点，则
$\sum_{i=0}^{h-1}2^i<n<=\sum_{i=0}^{h}2^i$
解得 h≈logn。建堆调整时，最后一层每个父节点最多需下调 1 次，共 2^(h-1) 个节点。倒数第二层每个父节点最多需下调 2 次，共 2^(h-2) 个节点。依次类推，顶点最多需下调 h 次，共 1 个节点。所以总共需下调的次数为
$\begin{equation} \begin{aligned} T(n) &=1*2^{h-1}+2*2^{h-2}+...+h*2^0\\ \end{aligned} \end{equation}$
可利用错位相减法计算 T(n)
$\begin{equation} \begin{aligned} 2T(n) &=1*2^{h}+2*2^{h-1}+3*2^{h-2}+...+\ \ h\ \ \ *\ \ \ \ \ 2^1\\ T(n) &=\ \ \ \quad\quad\quad1*2^{h-1}+2*2^{h-2}+...+(h-1)*2^1+h*2^0\\ T(n) &=1*2^h+1*2^{h-1}+1*2^{h-2}+...+\ \ 1\ \ \ \ *\ \ \ \ \ 2^1-h*2^0\\ &=\frac{2(1-2^h)}{1-2}-h\\ &=2^{h+1}-2-h,\ h=logn\\ &=2n-2-logn \end{aligned} \end{equation}$
所以建立大根堆的时间复杂度是 O(n)。建堆完成后还要进行 n-1 次向下调整，每次调整时间复杂度都是 O(h)，所以堆排序的最好、最坏和平均时间复杂度都是 O(nlogn)。

空间复杂度

算法使用了常数级空间，所以堆排序的最好、最坏和平均空间复杂度都是 O(1)。

总结

 类别            算法               时间复杂度               空间复杂度        稳定性
                              平均    最好       最坏
               直接插入       O(n^2)   O(n)     O(n^2)         O(1)            稳定
插入排序        折半插入       O(n^2)  O(n)      O(n^2)         O(1)            稳定
               希尔排序      O(n^1.3)  O(n)     O(n^2)         O(1)          不稳定

选择排序        直接选择      O(n^2)   O(n^2)    O(n^2)         O(1)          不稳定
               树形选择      O(nlogn) O(nlogn)  O(nlogn)       O(1)          不稳定

交换排序        冒泡排序       O(n^2)    O(n)    O(n^2)        O(1)            稳定
               快速排序      O(nlogn) O(nlogn)  O(n^2)       O(logn)         不稳定

归并排序                     O(nlogn) O(nlogn)  O(nlogn)       O(n)            稳定

对于稳定性，当排序过程中有非相邻元素交换，便会导致元素相对次序颠倒。希尔排序对序列分组，存在交叉移动。直接选择将未处理序列第一个元素与最小值交换，属于非相邻交换。堆排序采用树形结构，对子树向下调整，子树元素序号不一定连续。快速排序与直接选择类似。

几种简单排序中，直接插入的移动次数及冒泡排序的交换次数等于初始序列的逆序数，但冒泡排序赋值语句多于直接插入，而直接选择的交换次数与初始序列状态无关，但少于直接插入。因此，当数据规模较小时（n <= 50），若序列基本有序则选择直接插入，若元素对象比较复杂，且不考虑稳定性，为减少移动开销，因使用简单选择。

当数据规模较大时，不考虑稳定性，优选选择优化后的快速排序。因为快速排序和堆排序时间复杂度一致，虽然后者空间复杂度更低，但其有如下缺点：第一，堆排序访问数据的方式不如快排。快排的划分函数对数据是顺序访问的，而堆排序对数据是跳跃式访问的，这就不利于 CPU 缓存。第二，对于同一组数据，堆排序交换次数多余快排。因为快速排序数据交换的次数小于等于原始序列的逆序数。而归并排序无论是建堆还是删除堆顶都要向下调整，大多数情况下会导致逆序度增加。如果要选择稳定性算法，在内存充足的情况下，归并排序时间效率最高，内存紧张的情况下，使用希尔排序。

内部排序算法详解

排序算法的稳定性

快速排序

基本思想

稳定性

性能分析

最好时间复杂度

最坏时间复杂度

平均时间复杂度

空间复杂度

快速排序的优化

应用：寻找第 K 大数

归并排序

基本思想

稳定性

性能分析

时间复杂度

空间复杂度

插入排序

基本思想

稳定性

性能分析

最好时间复杂度

最坏时间复杂度

平均时间复杂度

空间复杂度

插入排序的优化

折半插入排序

希尔排序

选择排序

基本思想

稳定性

性能分析

时间复杂度

空间复杂度

冒泡排序

基本思想

稳定性

性能分析

最好时间复杂度

最坏时间复杂度

平均时间复杂度

空间复杂度

堆排序

基本思想

稳定性

性能分析

时间复杂度

空间复杂度

总结

参考文献