排序
Table of Contents
排序 #
前置知识 #
在计算机科学与数学中, 一个排序算法 (Sorting Algorithm) 是一种能将一串资料依照特定排序方式进行排列的一种算法.
根据数据量大小和存储容量的不同, 排序可以分为内部排序 (Internal Sorting)和外部排序 (External Sorting) . 内部排序中, 数据量通常较小, 内存可以加载所有数据并完成排序; 而在外部排序中, 数据量较大, 内存不足以一次性完全加载数据, 因此需要分块处理.
本文主要讨论对数组元素的内部排序, 这些元素本身存储在了物理线性结构 (Physically Linear Structure) 上. 排序问题的约定如下:
- 假定有 $N$ 个元素需要排序
- 以 C 语言的习惯为例, 数据下标从 $0$ 开始, 即待排序数组为 $A[0], A[1], …, A[N - 1]$
- 使用 $<$ 和 $>$ 作为比较运算符, 因此我们讨论的排序称为基于比较的排序 (Comparison-based Sorting)
选择排序 #
选择排序 (Straight Selection Sort) 是一种朴素的排序算法, 算法流程如下:
- 找到当前列表中最小的元素
- 把最小元素与列表第一个元素交换
- 对剩下的列表 (不含第一个元素的列表) 重复上面的操作, 直到列表为空
选择排序把列表分成了两个部分:
- 左列表, 由已经从小到大排序的元素构成 (前 $k$ 步后排好序的部分由原列表最小的 $k$ 个元素构成)
- 右列表, 由仍需排序的元素构成
计算复杂度为 $O(N^2)$ .
插入排序 #
插入排序 (Insertion Sort) 的算法流程如下:
- 遍历 $A[1], … A[N - 1]$ , 每次将 $A[k]$ 插入到前面的某个位置, 来保证前 $k + 1$ 个元素保持有序.
插入排序同样把列表分成了两个部分:
- 左列表, 由已经从小到大排序的元素构成 (前 $k$ 步后排好序的部分由原列表前 $k$ 个元素构成)
- 右列表, 由仍需排序的元素构成
注意选择排序与插入排序的区别.
计算复杂度: $O(N^2)$ . 与选择排序比较次数固定不同, 插入排序的比较次数不固定. 最坏情况为原数组完全逆序, 此时计算复杂度为 $O(N^2)$ ; 最好情况为原数组已排好序, 此时计算复杂度为 $O(N)$ .
折半插入排序 #
折半插入排序 (Binary Insertion Sort) 在插入排序的基础上优化了寻找插入位置的过程. 用二分查找替代原本的线性查找.
计算复杂度仍然是 $O(N^2)$ .
冒泡排序 #
冒泡排序 (Bubble Sort) 的算法流程如下:
- 有 $N - 1$ 步
- 每一步从左到右遍历未排序的数组, 如果 $A[j] > A[j + 1]$ , 交换两者.
冒泡排序每次将剩余数组中最大的元素转移到最右侧.
计算复杂度: $O(N^2)$
简单排序算法的复杂度下界 #
我们前面引入的几种排序算法, 都是依靠交换相邻元素完成排序的 (插入排序的插入过程在代码实现时也是由一系列相邻元素的交换构成) , 而这些排序算法的复杂度都是 $O(N^2)$ . 这是否意味着依赖相邻元素的交换算法复杂度下界是 $O(N^2)$ 呢? 下面来讨论这个问题.
逆序对 #
在一个数组中, 下标数对 $(i, j)$ 被称作一个逆序对, 如果:
- $i < j$
- $A[i] > A[j]$
对一个数组进行从小到大排序的过程, 本质上就是在不断消除数组中的逆序对. 交换相邻元素的操作等价于消除一个逆序对, 因此排序总共需要的交换次数等价于初始数组中逆序对的个数, 记为 $I$ .
复杂度下界 #
考虑一个数组平均有多少个逆序对. 长度为 $N$ 的数组共有 $\frac{N(N - 1)}{2}$ 个数对, 由对称性可以知道正序对和逆序对的平均数量一样, 因此长度为 $N$ 的数组平均有 $\frac{N(N - 1)}{4}$ 个逆序对, 这意味着依靠交换相邻逆序对进行排序的算法, 其计算复杂度至少是 $O(N^2)$ .
想要突破 $O(N^2)$ , 理论推导告诉我们不能局限于交换相邻元素, 有时候交换距离远一些的元素能够大大减少所需交换次数.
希尔排序 #
希尔排序 (Shell Sort) 是最早突破 $O(N^2)$ 的排序算法之一, 它可以看作是插入排序的改进算法. 希尔排序的算法流程如下:
- 根据固定的距离间隔 $h_k$ 将数组划分为几个子序列, 在各个子序列中分别进行比较和排序 (这一步通常由在 $h_k$ 个子序列分别使用插入排序完成, 因为插入排序在数据量较小时表现良好)
- 不断减少距离间隔并重复上述步骤
- 当距离间隔减少到 $1$ 时, 对整个数组进行基于相邻元素交换的排序
希尔排序的距离间隔序列 $h_t > h_{t - 1} > … > h_1$ 称为增量序列 (Increment Sequence). 在阶段 $k$ (增量为 $h_k$) 完成后, 对于每个 $i$ , 有 $A[i] \leq A[i + h_k]$ , 即所有的元素被分成了 $h_k$ 组分别排好了序, 此时我们称数组为 $h_k$ 排序好的. 希尔排序拥有一个重要的性质, 即一个 $h_k$ 排序好的数组在经过 $h_{k - 1}$ 排序操作后, 仍然是一个 $h_k$ 排序好的数组.
增量序列与时间复杂度 #
如何选取增量序列? 一个常见的方法是取 $h_t = \lfloor\frac{N}{2}\rfloor, h_k = \lfloor\frac{h_{k + 1}}{2}\rfloor$ , 不过这种取法效果一般.
如何选择最好的增量序列仍然没有得到理论上的解, 因此希尔排序的平均复杂度是一个悬而未决的开放问题. 使用一些特殊增量序列的希尔排序, 可以计算出最坏情况的复杂度:
- 选取 $1, 2, 4, …, 2^k$ 为增量序列, 最坏复杂度为 $O(N^2)$
- 选取 $1, 3, 7, …, 2^k - 1$ 为增量序列, 最坏复杂度为 $O(N^{\frac{3}{2}})$
归并排序 #
归并排序 (Merge Sort) 通过递归地合并两个排好序的数组来完成对原数组的排序, 它的算法流程如下:
- 把数组分为左右两个子数组
- 分别把两个子数组排序 (这一步也可以调用归并排序) , 合并两个排好序的数组
- 数组长度是 $1$ 则直接返回
“并” 的计算复杂度是 $O(N)$ , 空间复杂度也是 $O(N)$ . 递归至多有 $logN$ 次, 因此时间复杂度为 $O(NlogN)$ . 由于存储合并结果的数组 $TempArray$ 可以复用, 所以空间复杂度是 $O(N)$ .
归并排序是 “后序遍历” .
快速排序 #
快速排序 (Quick Sort) 是现有效率最高的排序算法之一, 它有如下优点:
- 平均时间复杂度为 $O(NlogN)$ . 最坏情况为 $O(N^2)$ , 但几乎遇不到这些情况.
- 空间复杂度为 $O(1)$
- 由递归分治的思想设计, 易于理解
快速排序的流程如下:
- 数组元素个数为 $0$ 或 $1$ 时, 直接返回
- 选择数组里的一个元素, 称作基准点 (pivot)
- 把去掉基准点的数组分为两部分, 一部分比基准点小, 一部分比基准点大
- 递归使用快速排序对两部分进行排序, 排好序的部分加上基准点构成排好序的原数组
快速排序的递归性质让算法过程看上去是在构建一棵二叉树. 不同于归并排序构造平衡二叉树, 快速排序本身不一定会构造出平衡二叉树, 对基准点的选择至关重要.
基准点的选取 #
选择第一个元素作为基准点是一个自然的想法, 但效果很不好. 在原数据近似有序或逆序的情况下, 选第一个元素作为基准点很可能把数组分成了大小差异巨大的两个集合, 最坏情况为 $O(N^2)$ ; 而现实世界的许多输入都是近似有序的.
随机选择基准点是个稳妥的方法, 但算法效率和随机数生成器的质量有关, 并且每次选择基准点也会有生成随机数带来的额外消耗.
最为理想的基准点是整个数组的中位数, 因为这样可以均匀地分割剩余的集合, 但得到整个数组的中位数很麻烦. 退一步, 我们随机抽三个元素, 取它们的中位数作为整个数组的中位数, 这是可行的, 但生成随机数带来的消耗同样不能忽视. 最终普遍采用的做法是三数中值分割法 (Median-of-Three Partitioning), 我们取数组最左侧、最中间和最右侧的元素的中位数作为基准点. '
元素移动 #
选取基准点的下一步是移动元素, 把数组分成两部分. 一个简单的办法是直接开额外的数组空间, 遍历一遍原数组把元素按相对基准点的大小存进去. 这种做法的空间开销太大, 因此通常使用双边循环的方法进行原地交换.
代码实现 #
首先是处理三数中值的函数 Median3() .
int Median3(int A[], int Left, int Right) { // 注意对 A[] 的修改对原数组有效
int Tmp; // 用于交换的临时变量
int Center = (Left + Right) / 2; // 中间元素坐标
if (A[Left] > A[Center]) { // 保证 A[Left] < A[Center]
Tmp = A[Left];
A[Left] = A[Center];
A[Center] = Tmp;
}
if (A[Left] > A[Right]) { // 保证 A[Left] < A[Right]
Tmp = A[Left];
A[Left] = A[Right];
A[Right] = Tmp;
}
if (A[Center] > A[Right]) { // 保证 A[Center] < A[Right]
Tmp = A[Center];
A[Center] = A[Right];
A[Right] = Tmp;
}
// A[Center] 为基准点, 交换基准点与 A[Right - 1]
Tmp = A[Center];
A[Center] = A[Right - 1];
A[Right - 1] = Tmp;
return A[Right - 1]; // 返回基准点的值
}
Median3() 函数在返回基准点值的同时, 保证了 $A[Left] < pivot < A[Right]$ , 而 $A[Right - 1]$ 用来存储基准点了, 我们的目的是将元素与 $pivot$ 比较并排序, 因此后续交换从 $i = Left + 1$ 与 $j = Right - 2$ 开始.
接下来看看整个快速排序的代码.
#define Cutoff (3) // 数据量较小时使用插入排序效率更高
void QSort(int A[], int Left, int Right) {
int i, j, Pivot, Tmp;
if (Left + Cutoff <= Right) {// 数据量较大时应用快速排序
Pivot = Median3(A, Left, Right); // 得到基准点值
i = Left; // 初始化 i 为 Left, 实际上为 Left + 1 也不影响结果
j = Right - 1; // 初始化 j 为 Right - 1, 实际上为 Right - 2 也不影响结果
for (;;) { // 循环交换元素
while (A[++i] < Pivot) {}; // 向右找到第一个 A[i] > Pivot
while (A[--j] > Pivot) {}; // 向左找到第一个 A[j] < Pivot
if (i < j) { // 如果 i < j, 那么交换消除逆序对
Tmp = A[i];
A[i] = A[j];
A[j] = Tmp;
} else break; // 如果 i > j, 退出循环
}
// 交换 A[i] 与 A[Right - 1], 因为 A[Right - 1] 在前面存储了 Pivot, 这里把基准点放回去
Tmp = A[i];
A[i] = A[Right - 1];
A[Right - 1] = Tmp;
QSort(A, Left, i - 1); // 递归处理左侧
QSort(A, i + 1, Right); // 递归处理右侧
}
// 数据量较小时应用插入排序
InsertionSort(A + Left, Right - Left + 1);
}
可以看出 Qsort() 的递归是先序遍历.
复杂度分析 #
记 $T(N)$ 为对长度为 $N$ 的数组进行快速排序所需的时间. $T(0) = T(1) = 1$ .
因为 Median3() 时间复杂度为 $O(1)$ , 遍历交换过程为 $O(N)$ , 所以有
$$
T(N) = T(i) + T(N - i - 1) + cN
$$
最坏情况是每次选出的基准点都是最小或最大的元素, 有 $T(N) = T(N - 1) + cN$ , 可以得到 $T(N) = O(N^2)$ .
最好情况是每次都均匀分割, 有 $T(N) = 2T(\frac{N}{2}) + cN$ , 即 $\frac{T(N)}{N} = \frac{\frac{T(N)}{2}}{\frac{N}{2}} + c$ , 可以得到 $T(N) = O(NlogN)$ .
考虑平均复杂度, 假定 $T(i)$ 均匀分布, 有 $$ T(i) = \frac{2}{N}\sum_{j = 0}^{N - 1}T(j) + cN $$
变形有 $$ NT(i) = 2\sum_{j = 0}^{N - 1}T(j) + cN^2 $$
用 $N - 1$ 代替 $N$ , 有 $$ (N - 1)T(i) = 2\sum_{j = 0}^{N - 2}T(j) + c(N - 1)^2 $$
两式相减, 有 $$ NT(N) - (N - 1)T(N - 1) = 2T(N - 1) + 2cN - c $$
渐进情况下我们认为 $2cN - c \approx 2cN$ 有 $$ NT(N) = (N + 1)T(N - 1) + 2cN $$
左右同时除以 $N(N + 1)$ , 有 $$ \frac{T(N)}{N + 1} = \frac{T(N - 1)}{N} + \frac{2c}{N + 1} $$
累加, 有 $$ \frac{T(N)}{N + 1} = \frac{T(1)}{2} + 2c\sum_{i = 3}^{N + 1}\frac{1}{i} $$
由于 $\sum_{i = 1}^{N}\frac{1}{i} = ln(N + 1) + γ$ , 故 $$ T(N) = O(NlogN) $$
排序算法的复杂度下界 #
在前面的算法中, 排序算法的时间复杂度最低是 $O(NlogN)$ . 而在理论上, 依靠成对比较 (Pairwise Comparison) 的排序算法在最坏情况下的最优复杂度正是 $O(NlogN)$ .
不管是什么排序算法, 其比较的逻辑都是一棵决策树 (Decision Tree) . 假定有 $N$ 个数需要排序, 那么总共可能有 $N!$ 种结果, 每次比较可以折半减少结果可能, 最终比较所需的次数等价于决策树的深度. 因为这颗二叉树有 $N!$ 个叶子节点, 因此深度至少为 $\lceil logN!\rceil$, 因此至少需要 $O(log(N!)) = O(NlogN)$ 次比较.
这是冰冷的理论告诉我们的下界. 不过, 如果有额外的信息, 人类的智慧可以突破 $O(NlogN)$ .
表排序 #
现实中, 我们经常需要依照某个键对大型结构体进行排序, 例如依照学号对学生信息进行排序. 与前面的排序不同的是, 对大型结构体进行数据交换的操作开销非常大, 因此对数据操作是一件不太可行的事. 一个更好的方法是创建一个指向这些结构体的指针数组, 依照键对指针数组进行排序. 例如结构体数组 $A[0], …, A[N - 1]$ , 创建 $T[0], …, T[N - 1]$ , 对 $T$ 排序, 使得 $A[T[0]].key < … < A[T[N - 1]].key$ .
在表排序完成的情况下, 如果需要改动结构体数据进行物理排序, 即需要把 $A[T[i]]$ 移动到 $A[i]$ 的位置上, 可以在 $O(N)$ 时间内完成. 注意到下标重排后可以分解成若干个不相交的环. 对于每个环, 把第一个元素对应的结构体存储到 $Temp$ 中, 再依次把后续的元素存到前一个元素的位置, 最后把 $Temp$ 填到空缺的位置上, 就完成了对这个环对应的结构体的物理排序. 时间复杂度 $O(N)$ , 空间复杂度 $O(1)$ .
桶排序 #
桶排序(Bucket Sort) 是一种针对整数 (或可以离散化) 的数据的排序方法, 要求知道数据的范围. 这里我们假定待排序数组 $A$ 的元素都是不重复的整数, 且范围为 $[1, M]$ .桶排序的算法流程如下:
- 创建一个数组 $Count$ , 最大下标至少为 $M$
- 遍历 $A$ 数组, 对于 $A[i]$ , 让 $Count[A[i]] = 1$
- 遍历完 $A$ 之后, 遍历 $Count$ 数组, 如果有 $Count[k] > 0$ , 输出 $k$ . 最终输出结果就是排好序的 $A$
桶排序的时间复杂度为 $O(M + N)$ , 需要额外 $O(M)$ 的空间. 这个排序的性能相当依赖数据的分布.
基数排序 #
基数排序 (Radix Sort) 可以看作桶排序的一个推广, 它也被称作扑克排序 (Poker Sort) 或分布排序 (Distribution Sort) .
基数排序相较于桶排序在空间消耗上减小了很多. 它的算法流程如下:
- 创建一个长度为 $1$ 的桶数组
- 在第 $k$ 轮排序中, 将从左到右将第 $k$ 位为 $i$ 个元素放入桶 $i$ 中
- 最高位排序完成后, 按顺序输出桶中元素就得到原数组的排序结果
基数排序的时间复杂度为 $O(P(N + B))$ , 其中 $P$ 是数据的最高位数, $N$ 是元素个数, $B$ 则则是桶的数量.
外部排序 #
前面讨论的主要是内部排序, 在内存中进行比较与交换操作速度非常快. 但是, 当数据量过大以至于内存不能一次加载所有数据时, I/O 操作耗费的时间会远远高于内存中操作耗费的时间.
简单归并排序 #
把数据拆分成许多份, 分别在内存中排好序, 再进行合并操作. 合并时不可避免地会在 I/O 上耗费大量时间.