第七章 - 排序

约 1996 个字 11 行代码预计阅读时间 7 分钟

概念

排序 (sorting) 是指一类将一组特定的数据按某种顺序进行排列的算法。

稳定性 (stability) 是指相等的元素经过排序之后相对顺序不发生改变的性质。具有稳定性的排序算法会让原本有相等键值的纪录维持相对次序。根据具有稳定性与否，我们可以将所有排序算法分为以下两类：

稳定排序：计数排序、插入排序、冒泡排序、归并排序
不稳定排序：选择排序、堆排序、快速排序、希尔排序

在下文中，我们约定序列的长度为 $N$，每个位置的编号为 $0$ 到 $N - 1$。

插入排序

最简单的排序算法之一是插入排序 (insertion sort)，其由 $N - 1$ 趟 (pass) 排序组成。

具体地，对于第 $P$ 趟排序，其中 $0 \leq P \leq N - 1$，我们将位置 $P$ 处的元素顺次与位置 $0$ 到位置 $P - 1$ 处的元素比较，并将其插入到正确的位置。不难发现，这种操作保证了在第 $P$ 趟排序时，位置 $0$ 到位置 $P - 1$ 处的元素是已经排序完毕的。插入排序的正确性也是由这一点保证的。

我们给出插入排序的例程：

void InsertionSort(ElementType A[], int N) {
    int j, P;
    Element Type Tmp;
    for (P = 1; P < N; P++) {
        Tmp = A[P];
        for (j = P; j > 0 && A[j - 1] > Tmp; j--) {
            A[j] = A[j - 1];
        }
        A[j] = Tmp;
    }
}

根据例程我们也可以容易分析出，插入排序在平均情形下的时间复杂度为 $O(N^{2})$。

简单排序算法的下界

一个数列的逆序 (inversion) 是指数列中满足 $i < j, A[i] > A[j]$ 的序偶 $(A[i], A[j])$。

在简单排序算法中，交换两个不按原序排列的相邻元素恰好消除一个逆序，一个排序完成的数列没有逆序，因此排序算法的时间复杂度和逆序数有关。具体地说，如果原始数列中的逆序数为 $I$，且算法中还有 $O(N)$ 的其它工作，则该简单排序算法的时间复杂度即为 $O(I + N)$。

为考察平均情况下的排序算法效率，我们给出如下有关逆序数的定理：

$N$ 个互异数的数组的平均逆序数为 $\frac{N (N - 1)}{4}$。

这个定理意味着插入排序平均是二次的，进一步地，其为所有只交换相邻元素的算法给出了一个下界：

通过交换相邻元素进行排序的任何算法平均需要 $\Omega (N^{2})$ 时间。

这个下界指出，为了使一个排序算法以亚二次 (subquadratic) 或 $o(N^{2})$ 时间运行，就必须执行一些比较，使得能够对相距较远的元素进行交换。

希尔排序

从前文的思路出发，希尔排序 (Shellsort) 是一个很自然的改进排序算法。

算法思路

希尔排序通过比较相距一定间隔的元素来工作，每一轮比较所用的举例随着算法的进行而减小，直到只比较相邻元素的最后一轮排序为止。基于其实现方式，希尔排序也被称作缩小增量排序 (diminishing increment sort)。

具体地，希尔排序使用一个序列 $h_{1}, h_{2}, \cdots, h_{t}$，该序列称作增量序列 (increment sequence)。只要保证 $h_{1} = 1, h_{k} < h_{k + 1}$，满足这两点的任何增量序列都是可行的。于是我们依次令 $h = h_{t}, h_{t - 1}, \cdots, h_{1}$，逆序地使用增量序列以进行 $t$ 轮排序。

在每一轮排序中，我们将原序列 $\{a_{1}, a_{2}, \cdots a_{n}\}$，按照 $h$ 的距离划分为 $h$ 个子序列，即 $\{a_{1}, a_{1 + h}, \cdots a_{1 + k_{1}h}\}, \{a_{2}, a_{2 + h}, \cdots a_{2 + k_{2}h}\} \cdots \{a_{h}, a_{2h}, \cdots a_{(1 + k_{h}) h}\}$，并对每个子序列进行插入排序。

如此进行 $t$ 轮后，由于 $h_{1} = 1$，即最后一轮排序是一轮插入排序，这一算法的正确性是显然的。

复杂度分析

虽然希尔排序的思路简单，但是其时间复杂度分析是很复杂的。容易看出，这一算法的时间复杂度主要取决于对增量序列的选取，简明起见，我们直接给出不同增量序列对应的时间复杂度，其证明参阅教材和网络资料。

若增量序列为 $\{h_{k} | h_{k} = 2^{k} - 1, h_{k} \leq N\}$，即希尔增量，则希尔排序的平均复杂度为 $O(N^{\frac{3}{2}})$，最坏复杂度为 $O(N^{2})$。

若增量序列为 $\{h_{k} | h_{1} = 1, h_{k + 1} = 2 h_{k} + 1, h_{k} \leq N\}$，即 Hibbard 增量，则希尔排序的平均复杂度为 $O(N^{\frac{5}{4}})$，最坏复杂度为 $O(N^{\frac{3}{2}})$。

若增量序列为 $\{h_{k} | h_{1} = 1, h_{k} = 4^{k} - 3 \cdot 2^{k} + 1 (k = 2, 3, \cdots), h_{k} \leq N\}$，即 Sedgewick 增量，则希尔排序的平均复杂度为 $O(N^{\frac{7}{6}})$，最坏复杂度为 $O(N^{\frac{4}{3}})$。

若增量序列为 $\{h_{k} | h_{k} = 2^{p} 3^{q}, p, q \in \mathbb{N}, h_{k} \leq N\}$，则希尔排序的平均复杂度为 $O(N \log^{2} N)$。

堆排序

基于数据结构以实现高效排序的思路也是容易想到的，一个常用的方式即为利用我们在第四章中讨论的堆。

我们知道，堆可以用一个数组表示，于是我们可以直接将要排序的数组看作一棵树。接下来便只需要两个步骤：

从树的倒数第二层开始，对每一层的每一个节点倒序执行下滤操作，使序列具有堆序性。
不断取出堆顶元素，并执行 DeleteMin 或 DeleteMax 操作。

从代码实现上来说，我们更倾向于建立 max 堆，这样就可以简单地把每次提取出的堆中的最大元素从后向前地放入原数组中。在这种方式下，堆排序只需要 $O(1)$ 的额外空间，取得了非常优秀的空间复杂度。

考察堆操作的的时间复杂度，容易得到堆排序的时间复杂度为 $O(N \log N)$。更进一步地，其最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 $O(N \log N)$。

归并排序

归并排序 (mergesort) 是另一种优秀的分治算法。

这一算法的核心在于「合并」操作，具体地，将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。只需从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。为保证排序的稳定性，在前段首元素 a[i] 小于等于后段首元素 b[j] 时而非小于时，就要作为最小值放入 c[k]。

于是，归并排序只需要以下两个步骤：

当数组长度为 $1$ 时，该数组就已经是有序的，不用再分解。
当数组长度大于 $1$ 时，将该数组分为两段，再分别检查两个数组是否有序。如果有序，则将它们合并为一个有序数组；否则对不有序的数组重复第 2 步，再合并。

用数学归纳法可以证明以上两步可以将一个数组转变为有序数组。

为保证排序的复杂度，通常将数组分为尽量等长的两段。在这种分割方法下，归并排序的时间复杂度为 $O(N \log N)$。

需要注意的是，基于「合并」操作的需要，归并排序往往需要 $O(N)$ 的额外空间。

快速排序

快速排序 (quicksort) 是非常重要的排序算法，也是已知的在实践中最快的排序算法，可以达到 $O(N \log N)$ 的平均时间复杂度。

算法步骤

快速排序同样是一种分治的递归算法，具体来说有以下四步：

若 $S$ 中元素个数为 $0$ 或 $1$，则返回。
取 $S$ 中任意元素 $v$，称为枢纽元 (pivot)。
将 $S - \{v\}$（$S$ 中除 $v$ 以外的其它元素）分为两个不相交集合：$S_{1} = \{x \in S - \{v\} | x \leq v\}, S_{2} = \{x \in S - \{v\} | x \geq v\}$。
将 $S$ 排序为 $\{\texttt{quicksort}(S_{1}), v, \texttt{quicksort}(S_{2})\}$。

容易意识到，快速排序的效率主要取决于对枢纽元 $v$ 的选取上。自然地，我们希望每次选取 $v$ 后得到的 $S_{1}, S_{2}$ 是尽量等长的，于是就能得到最佳的时间复杂度。

接下来我们将具体讨论算法中的一些细节。

选取枢纽元

一个有效的且时间成本不影响整体复杂度的选取方法，称作三数中值分割法 (Median-of-Three Partitioning)。

具体地，我们每次选取序列左端、右端、中间位置的三个元素的中值为枢纽元。

当然另一种合理的方法就是随机选取枢纽元，这也能保证快速排序的平均时间复杂度。

分割策略

在算法的整体思路中，「分割」似乎是相对简明的一步。但是在具体的代码实现中，这一步骤却不容易写对，或者采用了错误的方法会使其时间复杂度退化。因此，给出一个正确的、步骤明确的分割策略使非常重要的。在下文的讨论中，我们会伴随使用一个实例加以说明。

第一步，将枢纽元与序列中最后一个元素交换，使得枢纽元离开要被分割的序列。同时创建两个指针 $i, j$，分别指向序列中的第一个元素和倒数第二个元素。

第二步，当 $i$ 在 $j$ 左边时，我们将 $i$ 右移，移过小于枢纽元的元素；将 $j$ 左移，移过大于枢纽元的元素。当 $i$ 和 $j$ 停止时，$i$ 指向一个大于枢纽元的元素而 $j$ 指向一个小于枢纽元的元素。如果 $i$ 仍然在 $j$ 左边，则将它们分别指向的元素互换。不断重复这一过程直到 $i$ 与 $j$ 重合或位于 $j$ 右边。

第三步也是最后一步，将枢纽元与 $i$ 所指向的元素交换。

容易验证，这样的分割策略总是可以得到正确的结果，并使得快速排序的总时间复杂度达到 $O(N \log N)$。唯一的问题在于，当序列中有较多与枢纽元相同的元素时，时间复杂度可能退化并达到最坏 $O(N^{2})$ 的结果。

大型结构的排序

在前文中，我们排序的对象都是一个数组，这便隐含了一个前提，即两个元素的交换的代价是很小的。但是在实际情况中，我们往往会对若干大型结构进行排序，例如若干个表格甚至数据库。此时对两个结构进行交换的代价是非常巨大的。

于是，一个常用的方法就是创建指向每个大型结构的指针，并记录排序使用的关键字。在排序中通过对指针进行排序以完成对大型结构的排序。这样的方式称作间接排序 (indirect sorting)。

排序的一般下界

在前文中，我们都是先提出具体的排序方法，再考察其复杂度。那么，我们是否可以通过考察「排序」这一问题的一般性质，从而得到所有排序方法的一般下界呢？

答案是肯定的，我们可以通过构建决策树 (decision tree) 来分析问题。同样出于笔记篇幅，我们直接给出最终结论：

任何只用到比较的排序算法在最坏情形下时间复杂度均为 $\Omega(N \log N)$
任何只用到比较的排序算法在平均情形下时间复杂度均为 $\Omega(N \log N)$

具体的推导读者可以参阅相关教材和网络资料。

桶式排序

至此，我们讨论了若干种基于比较的排序方法，并给出了这一类方法时间复杂度的一般下界。在本节中我们将表明，如果对于空间或其它因素做出让步，那么在线性时间内完成排序也是可能的。

桶式排序 (bucket sort) 是一个经典的例子，其实现方式也非常简单。如果已知数组中所有元素均为小于 $M$ 的正整数，那么我们就创建一个大小为 $M$ 的 Count 数组并初始化全为零。之后对于数组中的每个元素 $a_{i}$，我们令 $\texttt{Count[} a_{i} \texttt{]}$ 增 $1$。最后我们只需从小到大扫描 Count 数组并输出即可。

容易得到，该算法的时间复杂度为 $O(\max\{N, M\})$，也就是存在线性的可能性。

基数排序

基数排序 (radix sort) 也是一种非比较型的排序方法。其将待排序的元素拆分为 $k$ 个关键字，通过逐一对每个关键字排序后完成对所有元素的排序。

如果是从第 $1$ 关键字到第 $k$ 关键字顺序进行比较，则该基数排序称作 MSD (Most Significant Digit first) 基数排序；反之则称作 LSD (Least Significant Digit first) 基数排序。

需要说明的是，基数排序的稳定性取决于其实现时内层选用的排序算法。如果这个内层排序算法是稳定的，那么基数排序也是稳定的；反之亦然。

总结

最后，我们对本章中所有排序算法做一个总结。

算法	平均时间复杂度	最坏时间复杂度	额外空间复杂度	是否仅基于比较	稳定性
插入排序	$O(N^{2})$	$O(N^{2})$	$O(1)$	√	√
希尔排序	$O(N \log^{2} N)$	$O(N^{{2}})$	$O(1)$	√
堆排序	$O(N \log N)$	$O(N \log N)$	$O(1)$	√
归并排序	$O(N \log N)$	$O(N \log N)$	$O(N)$	√	√
快速排序	$O(N \log N)$	$O(N^{2})	$O(N)$	√
桶式排序	$O(N)$	$O(N^{2})$	$O(M)$		取决于内层排序算法
基数排序	$O(MN \log N)$	$O(MN \log N)$	$O(M + N)$		取决于内层排序算法

算法	平均时间复杂度	最坏时间复杂度	额外空间复杂度	是否仅基于比较	稳定性
插入排序	\(O(N^{2})\)	\(O(N^{2})\)	\(O(1)\)	√	√
希尔排序	\(O(N \log^{2} N)\)	\(O(N^{{2}})\)	\(O(1)\)	√
堆排序	\(O(N \log N)\)	\(O(N \log N)\)	\(O(1)\)	√
归并排序	\(O(N \log N)\)	\(O(N \log N)\)	\(O(N)\)	√	√
快速排序	\(O(N \log N)\)	$O(N^{2})	\(O(N)\)	√
桶式排序	\(O(N)\)	\(O(N^{2})\)	\(O(M)\)		取决于内层排序算法
基数排序	\(O(MN \log N)\)	\(O(MN \log N)\)	\(O(M + N)\)		取决于内层排序算法