Appearance
外部排序
为什么需要外部排序
当待排序的数据量非常大，无法一次性全部装入内存时，就不能使用内部排序算法（如快排、归并等）。例如一个 10GB 的文件，而内存只有 512MB，此时必须借助外存（磁盘）来完成排序，这就是外部排序。
外部排序的核心瓶颈在于磁盘 I/O，因为磁盘读写速度远低于内存操作。因此，外部排序算法的设计目标是尽量减少磁盘 I/O 次数。
核心思想
外部排序的基本策略：
- 生成初始归并段（Run）：将大文件分成若干段，每段读入内存进行内部排序，排好序后写回外存，形成有序的初始归并段
- 多路归并：对所有初始归并段进行多趟归并，每趟将若干个有序段合并为更大的有序段，直到整个文件有序
- 优化方向：减少归并趟数、减少每趟的 I/O 次数、加速归并过程中的比较操作
外部排序的总 I/O 次数 = 初始归并段生成的 I/O + 归并阶段的 I/O。归并阶段的 I/O 次数与归并趟数直接相关，因此减少趟数是关键。
交互可视化
通过下方的交互动画，你可以逐步观察外部排序的执行过程：
操作详解
外部排序的概念
外部排序的基本流程分为两个阶段：
- 生成初始归并段：假设文件共有 N 条记录，内存工作区可容纳 M 条记录。每次读入 M 条记录到内存，用内部排序算法排好序后写回磁盘，共生成 m = ⌈N/M⌉ 个初始归并段
- 多路归并：对 m 个初始归并段进行 k 路归并，每趟将 k 个有序段合并为一个更大的有序段，经过多趟归并后得到最终有序文件
文件(N条记录)
↓ 内部排序
[段1] [段2] [段3] ... [段m] ← m个初始归并段
↓ k路归并（第1趟）
[大段1] [大段2] ... ← ⌈m/k⌉个归并段
↓ k路归并（第2趟）
[更大段1] ... ← 段数继续减少
↓ ...
[最终有序文件]多路归并
设有 m 个初始归并段，采用 k 路归并，则归并趟数为：
S = ⌈log_k(m)⌉
这是外部排序最核心的公式。减少归并趟数 S 的两种途径：
| 策略 | 方法 | 效果 |
|---|---|---|
| 增大归并路数 k | 使用多路归并（如 5 路、10 路） | S = ⌈log_k(m)⌉ 随 k 增大而减小 |
| 减少初始归并段数 m | 使用置换-选择排序生成更长的归并段 | m 减小，S 随之减小 |
但增大 k 也有代价：在 k 路归并中，每次从 k 个段的当前元素中选最小值，简单方法需要 k-1 次比较，k 越大比较次数越多。解决方案是使用败者树，将每次选最小值的比较次数降为 ⌈log₂k⌉。
每趟归并需要将所有记录读一遍、写一遍，I/O 次数与数据总量成正比。因此：
总 I/O 次数 ∝ 归并趟数 S = ⌈log_k(m)⌉
败者树
败者树是一棵完全二叉树，用于加速 k 路归并中"从 k 个元素中选最小值"的过程。
工作原理：
- 叶子结点存放 k 个归并段的当前元素
- 内部结点记录"败者"（较大者）的来源编号
- 根结点之上额外有一个结点记录"冠军"（最小者）
- 每次取走最小元素后，只需沿该元素所在叶子到根的路径进行调整，比较次数为 ⌈log₂k⌉
败者树的关键优势：
| 选最小值方式 | 比较次数 | 适用场景 |
|---|---|---|
| 直接比较 | k-1 | k 较小时可用 |
| 败者树 | ⌈log₂k⌉ | k 较大时显著优于直接比较 |
例如 8 路归并：直接比较需 7 次，败者树只需 3 次。k 越大，败者树的优势越明显。
置换-选择排序
普通方法生成的初始归并段长度等于内存工作区大小 M。置换-选择排序可以生成平均长度为 2M 的初始归并段，从而减少归并段数量 m。
算法步骤：
- 从文件读入 M 条记录填满内存工作区（设为 WA）
- 从 WA 中选出最小的且不小于上一个输出记录的记录，输出到当前归并段
- 从文件读入下一条记录填补 WA 空位
- 重复步骤 2-3，直到 WA 中所有记录都小于上一个输出记录
- 当前归并段结束，开始生成下一个归并段
- 重复以上过程直到文件处理完毕
置换-选择排序生成的各个归并段长度通常不等，这引出了最佳归并树的问题。
最佳归并树（类似哈夫曼树）：
当各归并段长度不等时，归并顺序会影响总 I/O 次数。为使总 I/O 次数最少，应构造类似哈夫曼树的最佳归并树：
- 将每个归并段的长度作为叶子结点的权值
- 构造 k 叉哈夫曼树，权值大的归并段靠近根（晚参与归并）
- 带权路径长度最小 → 总 I/O 次数最少
注意：若初始归并段数量不足以构成严格的 k 叉哈夫曼树，需要补充长度为 0 的虚段。补虚段的条件：设 m 个初始归并段进行 k 路归并，若 (m-1) % (k-1) ≠ 0，则需补 k-1-(m-1)%(k-1) 个虚段。
复杂度分析
| 指标 | 公式/值 | 说明 |
|---|---|---|
| 归并趟数 | S = ⌈log_k(m)⌉ | m 为初始归并段数，k 为归并路数 |
| 每趟 I/O 次数 | 2 × ⌈N/B⌉ | N 为记录总数，B 为磁盘块容量（一读一写） |
| 总 I/O 次数 | S × 2 × ⌈N/B⌉ | 归并阶段的总磁盘读写次数 |
| 败者树每次选最小值 | ⌈log₂k⌉ 次比较 | 相比直接比较的 k-1 次显著减少 |
| 置换-选择排序平均段长 | 2M | M 为内存工作区大小 |
关键结论：外部排序的时间开销主要取决于磁盘 I/O 次数，而 I/O 次数与归并趟数成正比。
考研高频考点
- ⭐ 归并趟数公式 S = ⌈log_k(m)⌉ 的计算（选择题/填空题必考）
- ⭐ 增大归并路数 k 与减少初始归并段数 m 对趟数的影响（选择题高频）
- ⭐ 败者树的作用及比较次数 ⌈log₂k⌉（选择题/简答题）
- ⭐ 置换-选择排序生成初始归并段的过程（大题偶尔考）
- ⭐ 最佳归并树（k 叉哈夫曼树）的构造与虚段补充规则（大题高频）
- 外部排序总 I/O 次数的计算（填空题）
- 内部归并排序 vs 外部归并排序的区别（概念题）