Appearance
外部排序
数据量超过内存怎么办
当数据量大到内存放不下（比如 10GB 的文件），所有内部排序算法都失效了。外部排序的策略是：先把数据分成小块，每块在内存中排好序写回磁盘（生成初始归并段），然后用多路归并把所有归并段合并成最终有序文件。
408 考研中，外部排序是排序章节的收官内容，核心瓶颈在于磁盘 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 越大，败者树的优势越明显。
败者树手算示例
以 4 路归并为例，4 个归并段的当前元素分别为：
| 归并段 | b₀ | b₁ | b₂ | b₃ |
|---|---|---|---|---|
| 当前元素 | 5 | 12 | 3 | 9 |
第一步：初始建树
从叶子向上两两比较，败者（较大者）记录在内部结点，胜者继续向上比较：
叶子层: b₀(5) b₁(12) b₂(3) b₃(9)
第1轮比较: 5 vs 12 → 败者=b₁ | 3 vs 9 → 败者=b₃
胜者=b₀(5) 胜者=b₂(3)
第2轮比较: 5 vs 3 → 败者=b₀
胜者=b₂(3)
败者树结构:
[冠军: b₂(3)] ← 最小值
|
ls[0] = b₀ ← 记录败者来源
/ \
ls[1]=b₁ ls[2]=b₃ ← 记录败者来源
/ \ / \
b₀(5) b₁(12) b₂(3) b₃(9) ← 叶子（各段当前元素）冠军是 b₂(3)，即 4 个段中最小的元素是 3。
第二步：输出冠军，调整败者树
输出 3，从 b₂ 段读入下一个元素（假设是 7），只需沿 b₂ 到根的路径调整：
b₂ 的新元素: 7
沿路径向上比较:
ls[2] 存的败者是 b₃(9)，7 vs 9 → 新败者=b₃，胜者=b₂(7) 继续上
ls[0] 存的败者是 b₀(5)，7 vs 5 → 新败者=b₂，胜者=b₀(5) 继续上
新冠军: b₀(5)
调整后:
[冠军: b₀(5)]
|
ls[0] = b₂(7) ← 更新
/ \
ls[1]=b₁(12) ls[2]=b₃(9) ← 不变
/ \ / \
b₀(5) b₁(12) b₂(7) b₃(9)整个调整过程只比较了 2 次（= ⌈log₂4⌉），而不是重新从 4 个中选最小值的 3 次。
败者树的核心优势：每次输出一个元素后，调整只涉及从被替换叶子到根的一条路径，路径长度 = ⌈log₂k⌉。k 路归并共输出 n 个元素，总比较次数从 n(k-1) 降到 n⌈log₂k⌉。
置换-选择排序
普通方法生成的初始归并段长度等于内存工作区大小 M。置换-选择排序可以生成平均长度为 2M 的初始归并段，从而减少归并段数量 m。
算法步骤：
- 从文件读入 M 条记录填满内存工作区（设为 WA）
- 从 WA 中选出最小的且不小于上一个输出记录的记录，输出到当前归并段
- 从文件读入下一条记录填补 WA 空位
- 重复步骤 2-3，直到 WA 中所有记录都小于上一个输出记录
- 当前归并段结束，开始生成下一个归并段
- 重复以上过程直到文件处理完毕
置换-选择排序生成的各个归并段长度通常不等，这引出了最佳归并树的问题。
最佳归并树（类似哈夫曼树）：
当各归并段长度不等时，归并顺序会影响总 I/O 次数。为使总 I/O 次数最少，应构造类似哈夫曼树的最佳归并树：
- 将每个归并段的长度作为叶子结点的权值
- 构造 k 叉哈夫曼树，权值大的归并段靠近根（晚参与归并）
- 带权路径长度最小 → 总 I/O 次数最少
虚段补充规则
最佳归并树是一棵严格 k 叉树（每个内部结点恰好有 k 个孩子）。如果初始归并段数 m 不满足条件，直接构造会导致某次归并不满 k 路，降低效率。这时需要补充长度为 0 的虚段（不产生实际 I/O）。
推导过程：
设严格 k 叉树中，叶子结点数为 n₀（对应归并段），度为 k 的内部结点数为 nₖ，则：
- 结点总数：n = n₀ + nₖ
- 边数 = n - 1 = k·nₖ（每个内部结点贡献 k 条边）
- 联立得：nₖ = (n₀ - 1) / (k - 1)
因此 (n₀ - 1) 必须能被 (k - 1) 整除，否则无法构成严格 k 叉树。
判断规则：
设 u = (m - 1) % (k - 1)
- 若 u = 0：m 个归并段恰好构成严格 k 叉树，无需补虚段
- 若 u ≠ 0：需补充 (k - 1 - u) 个虚段（长度为 0 的段）
补充虚段后，叶子总数变为 m + (k-1-u)，满足严格 k 叉树条件。
真题示例（2019 统考真题）：
设外存上有 120 个初始归并段，进行 12 路归并时，需要补充多少个虚段？
计算：u = (120 - 1) % (12 - 1) = 119 % 11 = 9
需补充虚段数 = (12 - 1) - 9 = 2 个
验证：补充后叶子总数 = 122，(122 - 1) % 11 = 121 % 11 = 0，满足条件。
另一个例子：
8 个初始归并段，3 路归并。
u = (8 - 1) % (3 - 1) = 7 % 2 = 1 ≠ 0
需补充 (3 - 1) - 1 = 1 个虚段，叶子总数变为 9，(9 - 1) % 2 = 0，满足条件。
构造过程：将 1 个虚段（权值为 0）和权值最小的 2 个归并段先归并，然后按哈夫曼策略继续构造。
复杂度分析
| 指标 | 公式/值 | 说明 |
|---|---|---|
| 归并趟数 | 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 次数与归并趟数成正比。
易错：外部排序的性能瓶颈是磁盘 I/O 次数，不是比较次数。减少 I/O 的关键是减少归并趟数：归并趟数 = log_k(m)，其中 k 是归并路数，m 是初始归并段数。增大 k 或减少 m 都能减少趟数。
易错：增大归并路数 k 时，k 路归并每次需要从 k 个段中选最小值。直接比较需要 k-1 次比较，用败者树可以优化到 log2(k) 次。408 常考败者树在外部排序中的作用。
考研高频考点
- ⭐ 归并趟数公式 S = ⌈log_k(m)⌉ 的计算（选择题/填空题必考）
- ⭐ 增大归并路数 k 与减少初始归并段数 m 对趟数的影响（选择题高频）
- ⭐ 败者树的作用及比较次数 ⌈log₂k⌉（选择题/简答题）
- ⭐ 置换-选择排序生成初始归并段的过程（大题偶尔考）
- ⭐ 最佳归并树（k 叉哈夫曼树）的构造与虚段补充规则（大题高频）
- 外部排序总 I/O 次数的计算（填空题）
- 内部归并排序 vs 外部归并排序的区别（概念题）
相关知识
- 归并排序——外部排序基于归并思想，内部归并排序是理解外排的基础
- 堆排序——败者树/堆可用于加速多路归并中的"选最小值"操作
- B+树索引也是为磁盘设计的数据结构，与外部排序同属"面向磁盘"的算法设计思路
- 最佳归并树本质上是 k 叉哈夫曼树，需要掌握虚段补充规则