Internal Sorting Basics
排序的基本概念
排序：重新排列一组记录，使记录按照关键字递增或递减。
设输入记录为 $R_1,R_2,\dots,R_n$，对应关键字为 $k_1,k_2,\dots,k_n$。若按递增排序，输出应是输入记录的一个重排 $R’_1,R’_2,\dots,R’_n$，并满足：
$$
k’_1 \le k’_2 \le \dots \le k’_n
$$
注意三点：
- 排序对象是记录，比较依据是记录中的关键字。
- 关键字可以不唯一，所以排序时要考虑相同关键字记录的相对位置。
- 默认讨论递增排序；递减排序只是比较方向相反。
根据在排序过程中数据是否全部放入内容分为以下两类：
- 内部排序：待排序记录可以全部放入内存，算法主要关注时间复杂度、空间复杂度和稳定性。
- 外部排序：记录太多，无法一次全部读入内存，需要借助磁盘。外部排序除了内部处理时间，还必须重点考虑磁盘读写次数。
排序算法的评价指标
排序算法通常看三类指标。
| 指标 | 含义 | 注意 |
|---|---|---|
| 时间复杂度 | 关键字比较次数、记录移动次数 | 最好、平均、最坏情况可能不同 |
| 空间复杂度 | 额外辅助空间 | 是否原地排序 |
| 稳定性 | 相同关键字的相对先后是否保持不变 | 稳定不等于一定更好，要看需求 |
稳定性
稳定排序：若排序前 $R_i$ 在 $R_j$ 前面，且 $key_i=key_j$，排序后 $R_i$ 仍在 $R_j$ 前面。
不稳定排序：存在某种输入，使相同关键字记录的相对次序被改变。
| 排序算法 | 稳定性 | 关键原因 |
|---|---|---|
| 直接插入排序 | 稳定 | 只把严格大于待插入元素的记录后移，相等时停止 |
| 折半插入排序 | 稳定 | 相等时继续向右找，把新记录插到已有相等记录之后 |
| 希尔排序 | 不稳定 | 不同增量子表中的相等记录可能跨组移动 |
| 冒泡排序 | 稳定 | 相邻记录比较时，只交换严格逆序的一对 |
| 快速排序 | 不稳定 | 一趟划分可能把相等记录分到枢轴两侧并改变相对位置 |
| 简单选择排序 | 不稳定 | 每趟把最小记录与前部位置交换，可能跨过相等记录 |
| 堆排序 | 不稳定 | 建堆和调整堆会发生远距离交换 |
| 二路归并排序 | 稳定 | 合并两个有序表时，相等则先取左侧子表的记录 |
| 基数排序 | 稳定 | 每一趟分配与收集必须保持同一桶内的先后顺序 |
常见结论可以压缩成两组：
- 稳定：直接插入、折半插入、冒泡、归并、基数。
- 不稳定：希尔、快速、简单选择、堆。
稳定性的深层规律
稳定性的本质问题是：相等关键字的记录会不会被算法机制强行“跨越”。
容易保持稳定的机制：
- 只做相邻交换，且相等时不交换。例如冒泡排序只交换
a[j] > a[j+1]的相邻逆序对，相等元素不会互相越过。 - 只移动严格大于当前记录的元素。例如直接插入排序用
a[j] > temp，不使用a[j] >= temp。 - 合并时相等先取左边。例如二路归并中，左、右子表都已有序且各自稳定；遇到相等关键字时先取左侧记录，就能保留原相对顺序。
- 按桶收集时保留入桶顺序。例如基数排序每一趟必须稳定，否则低位已经建立的次序会被高位处理破坏。
容易破坏稳定性的机制：
- 远距离交换。希尔排序、快速排序、简单选择排序、堆排序都会让记录跨过一段区间，区间中若有相等关键字，就可能改变相对顺序。
- 把某个极值直接换到前面或后面。简单选择排序每趟找最小值再与当前首位交换，最小值可能从后面跨过一个相等关键字。
- 按结构调整而不是按原序移动。堆排序优先维护堆形，关键字相等的记录在上滤、下滤、交换堆顶时没有原序保护。
- 划分时只关心小于和大于枢轴。快速排序的一趟划分通常不保证相等元素仍按原来的先后进入左右区间。
稳定性不是排序算法天然的“品德”，而是具体实现的性质。同一种思想可以写出稳定或不稳定的变体；考研通常按教材中的经典实现判断。
排序方法总览
已整理的排序方法可以先按处理方式快速定位：
| 类别 | 常见算法 | 核心动作 |
|---|---|---|
| 插入类 | 直接插入、折半插入、希尔排序 | 将待排序元素插入到已有序部分 |
| 交换类 | 冒泡排序、快速排序 | 通过交换消除逆序 |
| 选择类 | 简单选择排序、堆排序 | 每趟选择一个极值放到最终位置 |
| 归并类 | 二路归并排序 | 合并多个有序子序列 |
| 分配类 | 基数排序、计数排序 | 按关键字或关键字位分配、计数 |
| 外部排序 | 外部归并排序、多路归并与败者树、置换-选择排序、最佳归并树 | 用内存缓冲区和多趟归并处理外存大文件 |
内部排序方法综合比较
这张表用于快速判断“某算法的基本性能”。
| 排序算法 | 最好时间 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 初始序列影响 |
|---|---|---|---|---|---|---|
| 直接插入排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 | 很大 |
| 折半插入排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 | 比较次数较稳定，移动次数仍受影响 |
| 希尔排序 | 与增量有关 | 与增量有关 | $O(n^2)$ | $O(1)$ | 不稳定 | 较大 |
| 冒泡排序 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 | 很大 |
| 快速排序 | $O(n\log_2 n)$ | $O(n\log_2 n)$ | $O(n^2)$ | 平均 $O(\log_2 n)$，最坏 $O(n)$ | 不稳定 | 很大 |
| 简单选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 | 小 |
| 堆排序 | $O(n\log_2 n)$ | $O(n\log_2 n)$ | $O(n\log_2 n)$ | $O(1)$ | 不稳定 | 小 |
| 二路归并排序 | $O(n\log_2 n)$ | $O(n\log_2 n)$ | $O(n\log_2 n)$ | $O(n)$ | 稳定 | 小 |
| 基数排序 | $O(d(n+r))$ | $O(d(n+r))$ | $O(d(n+r))$ | $O(r)$ 或 $O(n+r)$ | 稳定 | 小 |
| 计数排序 | $O(n+r)$ | $O(n+r)$ | $O(n+r)$ | $O(n+r)$ | 稳定版本稳定 | 小 |
折半插入排序减少的是比较次数，没有减少元素后移次数。即使初始序列已经有序，每趟仍要确定插入位置，整体时间通常仍按 $O(n^2)$ 记；若题目单独问比较次数，则约为 $O(n\log_2 n)$。
对 n 个互不相同的关键字排序，输入可能是 $n!$ 种不同排列中的任意一种。
基于比较的排序每次只比较两个关键字，例如判断 a < b 或 a > b。在关键字互异时，一次比较只有两种可能结果。因此，可以把一个比较排序算法抽象成一棵二叉判定树：
- 每个内部结点表示一次关键字比较。
- 左右分支表示该次比较的两种结果。
- 每个叶结点表示算法经过若干次比较后得到的一个最终排序结果。
若最坏情况下最多比较 k 次，则这棵二叉判定树的高度至多为 k，叶结点数最多为：
$$
2^k
$$
为了正确处理 $n!$ 种输入排列，叶结点至少要有 $n!$ 个：
$$
2^k \ge n!
$$
所以：
$$
k \ge \lceil \log_2(n!) \rceil
$$
利用：
$$
n! = 1\cdot2\cdot\cdots\cdot n
$$
取后一半因子可得：
$$
n! \ge \left(\frac{n}{2}\right)^{n/2}
$$
于是：
$$
\log_2(n!) \ge \log_2\left(\left(\frac{n}{2}\right)^{n/2}\right)
$$
$$
= \frac{n}{2}\log_2\frac{n}{2}
$$
$$
= \frac{n}{2}(\log_2 n - 1)
$$
当 n 足够大时，这就是 $\Omega(n\log_2 n)$。因此，任何基于比较的排序算法在最坏情况下都需要：
$$
\Omega(n\log_2 n)
$$
次关键字比较。
这说明：
受初始状态影响的算法
有些排序的效率与初始序列是否有序密切相关，有些则几乎不受影响。
| 受初始状态影响明显 | 原因 |
|---|---|
| 直接插入排序 | 逆序对越少，比较和移动越少；基本有序时效率高 |
| 冒泡排序 | 若带 swapped 标志，有序时一趟即可结束 |
| 快速排序 | 枢轴若每次极不平衡，递归树退化为单支 |
| 希尔排序 | 分组后的有序程度会影响每趟插入代价 |
| 受初始状态影响较小 | 原因 |
|---|---|
| 简单选择排序 | 每趟都要从剩余区间找最小或最大记录 |
| 堆排序 | 主要代价来自建堆和反复下坠调整 |
| 归并排序 | 每层都要完整归并，层数基本固定 |
| 基数排序 | 按关键字位分配与收集，趟数由关键字位数决定 |
| 计数排序 | 主要代价是计数、前缀和、回填 |
按应用场景选择排序方法
考试常把选择排序方法包装成“数据规模、存储结构、稳定性、初始状态、辅助空间限制”的判断题。
| 场景 | 优先考虑 | 理由 |
|---|---|---|
| $n$ 较小 | 直接插入排序、简单选择排序 | 实现简单，常数小 |
| 序列基本有序 | 直接插入排序、冒泡排序 | 可接近 $O(n)$ |
| 平均性能要求高，且不要求稳定 | 快速排序 | 平均 $O(n\log_2 n)$，实际效率通常好 |
| 最坏时间必须稳定在 $O(n\log_2 n)$，且辅助空间要小 | 堆排序 | 最坏仍为 $O(n\log_2 n)$，空间 $O(1)$ |
| 要求稳定，且能接受 $O(n)$ 辅助空间 | 归并排序 | 稳定，时间稳定为 $O(n\log_2 n)$ |
| 关键字范围较小的整数 | 计数排序 | 可达到 $O(n+r)$ |
| 多关键字、定长整数或字符串 | 基数排序 | 通过稳定的多趟分配收集完成排序 |
| 链表排序 | 直接插入排序、归并排序 | 插入和归并适合链式存储；折半插入、希尔、堆通常不适合链表 |
按限制条件反推算法
如果题目不给算法名，而给约束，可以按下面的规则缩小范围。
| 限制条件 | 可优先想到 |
|---|---|
| 必须稳定 | 直接插入、折半插入、冒泡、归并、基数、稳定计数 |
| 只能用 $O(1)$ 辅助空间 | 直接插入、折半插入、希尔、冒泡、快速、简单选择、堆 |
| 最坏时间要 $O(n\log_2 n)$ | 堆排序、归并排序 |
| 基本有序时希望最快 | 直接插入排序、带提前结束的冒泡排序 |
| 只要求移动次数少 | 简单选择排序 |
| 关键字不是比较型，而是小范围整数 | 计数排序 |
| 需要按低优先级到高优先级处理多关键字 | 基数排序的 LSD 思想 |
其他注意点
- “时间复杂度稳定”不等于“排序稳定”。堆排序时间稳定在 $O(n\log_2 n)$，但它不是稳定排序。
- “原地排序”通常指辅助空间为 $O(1)$，不等于完全没有变量。
- 快速排序平均最快，但最坏情况是 $O(n^2)$，递归栈最坏为 $O(n)$。
- 折半插入排序只减少比较次数，仍然需要移动元素，所以总时间仍是 $O(n^2)$。
- 简单选择排序比较次数与初始序列基本无关，但移动次数较少。
- 链表不能随机访问，不适合折半插入、希尔排序和堆排序这类依赖下标跳转或完全二叉树顺序存储的算法。
- 基数排序和计数排序不是基于关键字两两比较的排序，不受比较排序 $\Omega(n\log_2 n)$ 下界限制。