排序

排序算法的可视化，推荐前往 SortPedia ↗ 查看。

排序算法的评判#

性质#

稳定性#

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

稳定的排序能支持按不同键值多次排序。譬如对学生排序，要求按总分递减排序，若总分相同，按高数分数递减排序。具有稳定性的排序能胜任这个任务：先按高数分数递减排序，再按总分递减排序。这样，总分相同的同学，由于维持了前一次排序结果的相对位置不变，高数分数一定是递减的。

当然，通过设计比较函数，也可以让不稳定的排序做到上述双键排序的效果。

复杂度#

详见计算理论 ↗.

对于排序算法的空间复杂度，我们通常把数据本身占用的 $O(n)$ 空间与算法需要的额外辅助空间分离来看，并且主要关心后者。

原位排序是仅涉及序列内部交换的排序，不需要额外空间，空间复杂度不随问题规模增长，记为 $O(1)$.

基于比较的排序#

哦，现在，我的朋友，你必须想象自己已经失明了，你所能依靠的全部只有你的触觉，快去把面前这排羽毛球从好到坏摆放好，不然教练回来后会责备我们的。

来自 OI Wiki 的可视化动图：

$O(n^2)$ 的排序算法#

冒泡排序#

设 $A_{i .. n}$ 为当前还未排序的待处理区间。

每次从 $A_{i..n}$ 的最后开始向前遍历，如果前一个元素大于当前元素，就交换二者；然后把 $A_{i..n}$ 的左端点 $i$ 向后移动一位；直到 $A_{i..n}$ 为空。

由于只有严格不等时才会交换，因此等值元素永远不会「穿过」彼此，故冒泡排序是稳定的。

不难发现 $A_{1..n}$ 需要 $n$ 次才能缩小为空，而第 $i$ 次的区间长度为 $n-i+1$，因此总共遍历次数是一个等差数列求和，为 $O(n^2)$.

由于每次小的元素如同气泡浮到大的元素前面并堆积起来，和冒泡的过程很像，故而得名冒泡排序。

选择排序#

类似刚才，设 $A_{i .. n}$ 为当前还未排序的待处理区间。

每次将 $A_{i .. n}$ 中的最小值和 $A_{i .. n}$ 的首个元素（即第 $i$ 个元素）交换，并把 $i$ 右移一位；直到 $A_{i..n}$ 为空。

查找最小值的方法通常是遍历，因此选择排序的复杂度通常和冒泡排序一致。

根据查找最小值的方式和交换的方式，选择排序可以是稳定的也可以是不稳定的。

插入排序#

类似刚才，设 $A_{i .. n}$ 为当前还未排序的待处理区间。

每次取出 $A_{i..n}$ 的首个元素 $a_i$，并在已排好序的 $A_{1..i-1}$ 中查找第一个大于它的元素 $a_k$，然后将 $a_i$ 插入到 $a_k$ 前方，然后 $A_{k..i-1}$ 整体右移一位；把 $i$ 增加一位；直到 $A_{i..n}$ 为空。

由于「顺序查找」需要遍历 $A_{1..k}$，而「整体右移」需要移动 $A_{k..i-1}$，因此两个操作总体的次数为 $i$，时间复杂度与前两种排序一样，均为 $O(n^2)$.

但是插入排序可以通过两种方式优化：

• 顺序查找 → 二分查找
• 整体右移 → 链表插入

前者能把查找的复杂度降低到 $\log$ 级别；后者能把插入的复杂度降低到常数。

但很可惜，两种优化是互斥的，因为链表不支持随机访问，也就无法二分。因此总体的复杂度仍然是 $O(n^2)$. 这种互斥揭示了一种深层原理：数据结构“随机访问”与“动态插入”不可兼得。

$O(n\log n)$ 的排序算法#

和 $O(n^2)$ 的排序算法不同，如果要达到更低的时间复杂度，我们需要抛弃顺序处理区间的方式，而采用分治的方法。

快速排序#

设 $A_{l..r}$ 为当前正在处理的区间。

在 $A_{l..r}$ 中任选一个元素 $a_k$ 作为枢轴（pivot），将区间内所有元素小于等于枢轴的元素放在左边，大于等于枢轴的放在右边；然后递归地对左右两部分继续做同样的事，直到区间长度为 $0$ 或 $1$.

具体的划分过程有两种经典实现：Hoare 和 Lomuto. 它们均可在正比于区间长度的复杂度下进行原位划分，此处不再赘述。

在枢轴足够均匀的情况下（指大于枢轴和小于枢轴的元素数目的期望相同），每次子区间长度接近减半，因此递归深度为 $O(\log n)$，因此快速排序的平均时间复杂度为 $O(n \log n)$. 但若每次恰好选到了当前区间的最小值或最大值，则递归会退化成一条长链，整体过程变得极像选择排序或冒泡排序，此时时间复杂度会退化到 $O(n^2)$. 引入随机化选取枢轴有利于降低这种情况的发生概率。

由于划分时通常使用双指针，不能保证等值元素不互相穿过，因此快速排序一般是不稳定的。

归并排序#

设 $A_{l..r}$ 为当前还未排序的待处理区间。

每次将 $A_{l..r}$ 平均分成左右两半，分别递归排序，然后再将两个有序区间合并成一个更长的有序区间；直到区间长度为 $0$ 或 $1$.

合并两个有序区间时，只需要同时维护两个指针，每次取较小者放入结果序列即可，因此一次合并的复杂度与区间长度成正比。

又由于每一层区间长度都会减半，因此递归深度为 $O(\log n)$，故归并排序的时间复杂度始终是 $O(n \log n)$.

归并排序在合并时若总是优先取左侧相等元素，则可以保持相等元素的相对顺序不变，因此它是稳定的。
但由于合并过程通常需要额外的辅助数组来暂存结果，所以它不是原位排序。

堆排序#

关于堆的内容，详见 树形数据结构 ↗.

通过 Floyd 方法将整个序列原位建成一个大根堆，此时堆顶是最大值。

每次将堆顶元素与当前堆尾元素交换，并把堆的有效长度减一；再对新的堆顶执行下沉操作，恢复堆性质；直到堆中只剩下一个元素。

建堆的复杂度是 $O(n)$，而每次下沉的复杂度是 $O(\log n)$，一共进行 $n$ 次，因此堆排序的总时间复杂度为 $O(n \log n)$.

由于堆的调整过程中会频繁交换相距很远的元素，相等元素的相对顺序很容易被破坏，因此堆排序通常是不稳定的。

不基于比较的排序#

三种经典的不基于比较的排序，都利用了数字本身的索引特性和计算机硬件本身的随机访问能力。

桶排序#

对数据的值域进行划分，形成 $k$ 个桶。依次读入数据，并按照数据所在的区域放入对应的桶中。对桶内部应用其它排序，然后从小到大遍历所有桶并按序输出桶的内容。

如果直接开桶，空间复杂度可达 $O(nk)$. 如果使用动态空间，可以做到 $O(n+k)$ 的空间复杂度。

计数排序#

直接对数据的值域 $V$ 开计数器 cnt[V]（即值域中每个数字一个计数器），这就要求数据是整数（或者能映射为整数）。依次读入数据，并增加对应计数器的值。然后计算计数器数组的前缀和，得到每个值在输出序列的最大位置。

由于是最大位置，所以输出时从后向前遍历输入数据，将数据通过「计数器数组的前缀和」映射为「在输出序列的位置」，并输出到该位置；将计数器对应位置递减，表示下一个将会遇到的（也即更早输入的）等于该值的元素，其在输出序列的位置在更前面一位。

更详细的解释可参考计数排序 - OI Wiki ↗并结合其中给出的代码理解。

通过前缀和映射为排名的方式，我们保证了相同的值在排序前后相对位置不会交换。

不难看出，这要求数据的值域不能太大，否则计数器的数量会超过内存上限。

基数排序#

将待排序的数据拆分成多个键，并对每个键依次排序。对于数字，我们可以取每个数位作为键。

基数排序分为两种：LSD 和 MSD.

LSD (Least Significant Digit) 法：

先以最低有效键（如数字的个位）对数据排序，然后不断换用更高效力的键，反复排序直到最高有效键（如数字的最高位）。

在对每一个键进行排序时，必须使用稳定的排序算法（通常是计数排序或桶排序），否则高位的排序会破坏低位已经排好的相对顺序。

58734
94027
46308
58303
83025

58303
58734
83025
94027
46308

58303
46308
83025
94027
58734

83025
94027
58303
46308
58734

83025
94027
58303
58734
46308

46308
58303
58734
83025
94027

不难看出，基数排序消除了计数排序对值域 $V$ 的限制，通过将其拆分为多位，使得每一轮的计数器规模显著减小。

令 $d$ 为键的数量，一般来说接近 $\log V$. 令 $r$ 为每一个键的值域，接近 $V^{1/d}$. 一个等价关系是 $d \approx \log_r V$.

更多排序#

排序算法多种多样，还有很多这里来不及介绍。

这里补充一个可以高效并行计算的排序算法——双调排序 ↗。

排序的应用#

离散化#

如果需要对数据索引，但只关心数据的相对大小而不关心绝对大小，则可以先对数据排序并去重，然后重新将数据映射为其下标。这样，原先值域很大的数据就被映射到了区间 $[0,N-1]$，其中 $N$ 是数据的数量。

类似哈希，离散化适用于大值域稀疏数据，但离散化要求离线，且由于排序，复杂度通常比哈希高 $\log n$. 但是离散化不存在哈希冲突问题。

二分查找#

当数据被排序后，其单调性允许我们使用二分法快速定位某个元素，时间复杂度从顺序查找的 $O(n)$ 减小到 $O(\log n)$.

双指针#

在解决譬如「两数之和」的问题时，在排序后的数组上应用对撞双指针，可以把 $O(n^2)$ 的数对枚举降低到 $O(n)$. 此方法相比使用哈希，空间复杂度更低，但排序导致时间复杂度略高。

在统计众数时，可以在排序后的数组上应用滑动窗口，从而在 $O(n)$ 的时间内，不借助额外空间统计出区间众数。

分位数#

排序后的数组，其下标和分位数自然对应。

排序的应用远不止这些，很多贪心算法、搜索优化都需要借助排序实现。

附录#

贴一个总结表格，来自上课 PPT.