外部排序
含AI生成内容
外部排序
当数据量大到内存放不下时，所有内部排序算法都失效了。外部排序的策略：先把数据分成小块在内存中排序后写回磁盘（生成初始归并段），再用多路归并合并成最终有序文件。核心瓶颈在于磁盘 I/O。
基本流程
- 生成初始归并段：将大文件分成若干段，每段读入内存用内部排序排好序后写回外存
- 多路归并：对所有归并段进行多趟归并，直到整个文件有序
文件(N条记录) ↓ 内部排序[段1] [段2] ... [段m] ← m个初始归并段 ↓ k路归并[有序文件]归并趟数
设有 m 个初始归并段，采用 k 路归并：
S = ⌈log_k(m)⌉
减少归并趟数的两种途径：
| 策略 | 方法 | 效果 |
|---|---|---|
| 增大归并路数 k | 使用多路归并 | S 随 k 增大而减小 |
| 减少初始归并段数 m | 使用置换-选择排序 | m 减小，S 随之减小 |
总 I/O 次数 = S × 2 × ⌈N/B⌉，N 为记录总数，B 为磁盘块容量。
败者树
作用
在 k 路归并中加速”从 k 个元素中选最小值”的过程。
| 选最小值方式 | 比较次数 | 适用场景 |
|---|---|---|
| 直接比较 | k-1 | k 较小时 |
| 败者树 | ⌈log₂k⌉ | k 较大时显著优于直接比较 |
工作原理
- 叶子结点存放 k 个归并段的当前元素
- 内部结点记录”败者”（较大者）的来源编号
- 根结点之上记录”冠军”（最小者）
- 每次取走最小元素后，只需沿该路径调整，比较次数为 ⌈log₂k⌉
叶子层: 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)调整时只需沿被替换叶子到根的路径比较，4 路归并只需 2 次比较。
置换-选择排序
普通方法生成的初始归并段长度 = 内存工作区大小 M。置换-选择排序可以生成平均长度 2M 的初始归并段。
算法步骤：
- 从文件读入 M 条记录填满内存工作区 WA
- 从 WA 中选出最小的且不小于上一个输出记录的记录，输出到当前归并段
- 从文件读入下一条记录填补 WA 空位
- 重复直到 WA 中所有记录都小于上一个输出记录
- 当前归并段结束，开始生成下一个归并段
最佳归并树
当各归并段长度不等时，归并顺序影响总 I/O 次数。用类似哈夫曼树的方法构造 k 叉最佳归并树，权值大的归并段靠近根（晚参与归并），总 I/O 次数最少。
虚段补充规则
最佳归并树是严格 k 叉树（每个内部结点恰有 k 个孩子）。设初始归并段数为 m：
u = (m - 1) % (k - 1)
- u = 0：无需补虚段
- u ≠ 0：补充 (k - 1 - u) 个虚段（长度为 0）
真题示例（2019 统考）：
120 个初始归并段，12 路归并： u = (120-1) % (12-1) = 119 % 11 = 9 需补充 (12-1)-9 = 2 个虚段
复杂度
| 指标 | 公式/值 |
|---|---|
| 归并趟数 | S = ⌈log_k(m)⌉ |
| 每趟 I/O | 2 × ⌈N/B⌉（一读一写） |
| 败者树选最小值 | ⌈log₂k⌉ 次比较 |
| 置换-选择平均段长 | 2M |
⚠️ 易错：外部排序的性能瓶颈是磁盘 I/O 次数，不是比较次数。减少 I/O 的关键是减少归并趟数。
⚠️ 易错：增大归并路数 k 时，直接比较需要 k-1 次，用败者树可优化到 log₂k 次。
考研高频考点
- ⭐ 归并趟数公式 S = ⌈log_k(m)⌉ 计算
- ⭐ 增大 k 与减少 m 对趟数的影响
- ⭐ 败者树的作用及比较次数 ⌈log₂k⌉
- ⭐ 置换-选择排序生成初始归并段的过程
- ⭐ 最佳归并树构造与虚段补充规则
- 外部排序总 I/O 次数计算
- 内部归并排序 vs 外部归并排序的区别
关联页面
外部排序
当数据量大到内存放不下时，所有内部排序算法都失效了。外部排序的策略：先把数据分成小块在内存中排序后写回磁盘（生成初始归并段），再用多路归并合并成最终有序文件。核心瓶颈在于磁盘 I/O。
基本流程
- 生成初始归并段：将大文件分成若干段，每段读入内存用内部排序排好序后写回外存
- 多路归并：对所有归并段进行多趟归并，直到整个文件有序
文件(N条记录) ↓ 内部排序[段1] [段2] ... [段m] ← m个初始归并段 ↓ k路归并[有序文件]归并趟数
设有 m 个初始归并段，采用 k 路归并：
S = ⌈log_k(m)⌉
减少归并趟数的两种途径：
| 策略 | 方法 | 效果 |
|---|---|---|
| 增大归并路数 k | 使用多路归并 | S 随 k 增大而减小 |
| 减少初始归并段数 m | 使用置换-选择排序 | m 减小，S 随之减小 |
总 I/O 次数 = S × 2 × ⌈N/B⌉，N 为记录总数，B 为磁盘块容量。
败者树
作用
在 k 路归并中加速”从 k 个元素中选最小值”的过程。
| 选最小值方式 | 比较次数 | 适用场景 |
|---|---|---|
| 直接比较 | k-1 | k 较小时 |
| 败者树 | ⌈log₂k⌉ | k 较大时显著优于直接比较 |
工作原理
- 叶子结点存放 k 个归并段的当前元素
- 内部结点记录”败者”（较大者）的来源编号
- 根结点之上记录”冠军”（最小者）
- 每次取走最小元素后，只需沿该路径调整，比较次数为 ⌈log₂k⌉
叶子层: 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)调整时只需沿被替换叶子到根的路径比较，4 路归并只需 2 次比较。
置换-选择排序
普通方法生成的初始归并段长度 = 内存工作区大小 M。置换-选择排序可以生成平均长度 2M 的初始归并段。
算法步骤：
- 从文件读入 M 条记录填满内存工作区 WA
- 从 WA 中选出最小的且不小于上一个输出记录的记录，输出到当前归并段
- 从文件读入下一条记录填补 WA 空位
- 重复直到 WA 中所有记录都小于上一个输出记录
- 当前归并段结束，开始生成下一个归并段
最佳归并树
当各归并段长度不等时，归并顺序影响总 I/O 次数。用类似哈夫曼树的方法构造 k 叉最佳归并树，权值大的归并段靠近根（晚参与归并），总 I/O 次数最少。
虚段补充规则
最佳归并树是严格 k 叉树（每个内部结点恰有 k 个孩子）。设初始归并段数为 m：
u = (m - 1) % (k - 1)
- u = 0：无需补虚段
- u ≠ 0：补充 (k - 1 - u) 个虚段（长度为 0）
真题示例（2019 统考）：
120 个初始归并段，12 路归并： u = (120-1) % (12-1) = 119 % 11 = 9 需补充 (12-1)-9 = 2 个虚段
复杂度
| 指标 | 公式/值 |
|---|---|
| 归并趟数 | S = ⌈log_k(m)⌉ |
| 每趟 I/O | 2 × ⌈N/B⌉（一读一写） |
| 败者树选最小值 | ⌈log₂k⌉ 次比较 |
| 置换-选择平均段长 | 2M |
⚠️ 易错：外部排序的性能瓶颈是磁盘 I/O 次数，不是比较次数。减少 I/O 的关键是减少归并趟数。
⚠️ 易错：增大归并路数 k 时，直接比较需要 k-1 次，用败者树可优化到 log₂k 次。
考研高频考点
- ⭐ 归并趟数公式 S = ⌈log_k(m)⌉ 计算
- ⭐ 增大 k 与减少 m 对趟数的影响
- ⭐ 败者树的作用及比较次数 ⌈log₂k⌉
- ⭐ 置换-选择排序生成初始归并段的过程
- ⭐ 最佳归并树构造与虚段补充规则
- 外部排序总 I/O 次数计算
- 内部归并排序 vs 外部归并排序的区别
关联页面
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
评论区
