Lecture 29：排序
Chinese-language Computer Science 408 note: Lecture 29：排序. Original source available where applicable.
On this page
This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.
排序是把记录按关键字重新排列为有序序列。408 中不只问“结果是否有序”，还常考稳定性、存储位置、时间/空间复杂度，以及外存场景下的 I/O 代价。
29.1 排序的基本概念
定义：#排序
描述：排序是将一组记录按关键字的非递减（或非递增）次序重新排列的过程。默认升序时，结果满足：
$$ K_1\le K_2\le\cdots\le K_n $$
- 排序对象是记录，关键字只是排序依据；交换或移动时记录的其他字段应随关键字一起移动。
- 关键字可以重复，因此“有序”并不能唯一确定所有记录的相对次序；这正是稳定性的意义。
- 题目未说明升降序时，要先结合比较条件或最终序列判断，不能把算法名直接等同于升序。
29.1.1 稳定性
定义：#稳定排序
描述：若排序前两个记录 $R_i,R_j$ 满足 $key_i=key_j$ 且 $R_i$ 在 $R_j$ 之前，排序后 $R_i$ 仍在 $R_j$ 之前，则该排序算法稳定；否则不稳定。
- 稳定性只讨论关键字相等的记录；关键字不同的记录相对位置改变是排序的正常目的。
- 当记录还有次关键字或附带信息时，稳定排序可保留原来的次序。例如先按姓名排序、再稳定地按班级排序，可保留同班同学的姓名序。
- 同一算法的稳定性取决于实现细节。典型例子：归并时相等元素优先取左表元素才稳定；冒泡仅在
A[j-1] > A[j]时交换才稳定。 - 判定某个具体实现“不稳定”，只需构造一组相等关键字次序被颠倒的反例；但某一次运行恰好没有颠倒相等元素，不能据此证明算法稳定，稳定性要求对所有合法输入都成立。
紫色 $3$ 原先在红色 $3$ 前：左侧排序结果仍保持这个次序，右侧结果把两者颠倒。注意图中比较的是两条记录的身份，不只是数值都等于 $3$。
29.1.2 衡量排序算法
| 指标 | 关注内容 |
|---|---|
| 时间复杂度 | 关键字比较、记录移动、递归等总耗时的量级 |
| 空间复杂度 | 排序过程额外占用的存储空间 |
| 稳定性 | 相等关键字记录的相对次序是否保持 |
| 适用存储结构 | 是否依赖随机访问、连续数组或链式结构 |
| 外存 I/O | 数据无法全部装入内存时，读写磁盘块的次数 |
- “比较次数少”不必然意味着整体更快：插入排序即使通过二分减少比较，记录后移仍可能达到 $O(n^2)$。
- “原地”有两种常见口径：严格按全部辅助空间计，只有 $O(1)$ 才算原地；若仅指在原数组内划分、不另开线性缓冲区，递归快排也常被称作原地。无论采用哪种说法，递归栈都须单独计入：快排平均 $O(\log n)$、最坏 $O(n)$，不能把整套递归实现误写为 $O(1)$ 辅助空间。
29.2 内部排序与外部排序
29.2.1 内部排序
定义：#内部排序
描述：待排序记录在排序过程中可全部放入内存的排序，称为内部排序。
- 主要分析比较、移动、递归和辅助数组等内存代价。
- 本章的插入、交换、选择、归并、基数排序均可作为内部排序算法讨论。
- 数据量并非按文件大小绝对划分，而看可用内存能否同时容纳待排数据。
29.2.2 外部排序
定义：#外部排序
描述：待排序数据量过大，无法一次全部读入内存，需要在外存与内存之间分批读写并完成排序，称为外部排序。
- 外存以块为单位读写，数据必须先进入内存才能比较和修改。
- 外部排序通常先生成多个有序的初始归并段，再做多路归并。
- 磁盘 I/O 远慢于内存运算，所以优化重点是减少归并趟数和读写块次数，而不仅是减少关键字比较。
相关知识
29.3 本节复盘
- 排序将记录按关键字有序排列；记录的其他字段必须随记录整体移动。
- 稳定性只针对相等关键字：原先靠前者排序后仍靠前才稳定。
- 内部排序关注时间和空间，外部排序还要重点计算磁盘块 I/O。
- 后续做算法对比题时，至少同时检查稳定性、最坏复杂度、辅助空间与存储结构前提。