掌握外部排序的初始归并段生成和多路归并流程,模拟置换选择排序,并理解败者树、归并路数与磁盘 I/O 次数的关系。
# 一、外部排序的基本流程
当全部待排序记录无法同时装入内存时,需要借助外存完成排序。外部排序主要受磁盘块读写次数影响,而不是只比较 CPU 内部的关键字比较次数。典型流程分为:
- 生成初始归并段:把数据分批读入内存,生成各自有序的子文件。
- 多路归并:每次把 个有序段合并为一个更长的有序段,反复进行直到只剩一个段。
flowchart LR
A[外存无序文件] --> B[生成若干有序初始段]
B --> C[多路归并一趟]
C --> D{是否只剩一个有序段}
D -->|否| C
D -->|是| E[得到完整有序文件]若一趟读入并写出整个文件,文件含 个记录、每个磁盘块含 个记录,则一次归并趟约需读写 个块传送;归并趟数直接影响总 I/O。
# 二、置换选择排序生成初始段
置换选择排序(Replacement Selection)使用容量为 的内存工作区,边输出当前归并段、边读入新记录。其核心是尽量让新读入的记录继续进入当前有序段。
- 把输入文件开头的 个记录放入工作区,按关键字组织为最小堆。
- 取出并输出堆顶最小记录,记当前归并段最后输出值为 。
- 从输入文件读入一个新记录 :
- 若 ,它仍可加入当前归并段;
- 若 ,它不能放在当前段末尾,冻结到下一归并段。
- 在活动记录中继续输出最小者;当前活动集合为空时结束本段,启用冻结记录开始下一段。
- 重复直至输入和工作区均处理完。
对随机输入,一个初始归并段的平均长度约为 ,通常比 “每次只把 条记录装入内存、内部排序后输出一段” 的长度更大;具体长度随输入次序变化,并不保证一定达到 。
例题 8.1:置换选择的冻结判断
工作区容量为 ,当前归并段最后输出的关键字为 。新读入 时,它仍可加入当前段;新读入 时,它小于 ,必须冻结到下一段。冻结记录仍保留在工作区,但暂不参加当前段的最小值选择。
# 三、多路归并
设有 个初始归并段。 路归并每次从 个段各读取一个当前记录,取其中最小值输出,再从该记录所属段补入下一个记录。
- 直接逐个比较 个当前记录,每输出一个记录需 次比较。
- 用最小堆或胜者树 / 败者树维护当前候选值,每次输出和更新通常需 次比较。
- 归并树的叶子对应输入归并段,根位置的胜者代表当前全局最小值。
败者树在内部结点保存比较中落败的一方,当前最小者单独作为胜者保存。某一输入段读入新记录后,只需沿它到根的路径逐层重赛,调整代价为 。胜者树、败者树都是多路归并的选择树实现。
多路归并需要为每个输入段准备缓冲区,并为输出准备缓冲区,因此可用路数受内存中可容纳的输入、输出缓冲块数限制。增大 可减少归并趟数,但需要更多输入缓冲空间。
# 四、归并趟数与 I/O
若每趟最多合并 个归并段,初始有 个归并段,理想情况下归并趟数约为
实际分组需满足每个归并段在每趟恰好参与一次合并,尾组不足 段时也要按规则处理。若每趟都读取并写出全文件,则总块传送次数约为
尚未计入初始段生成阶段的读写,也未考虑最后一趟直接输出而省略写回等实现差异。分析题要明确题目问的是归并趟数、磁盘读写次数还是块传送次数。
# 五、考场检查清单
- 外部排序先形成有序初始段,再做多路归并。
- 置换选择中,新记录不小于当前段最后输出值时可留在当前段;较小时冻结到下一段。
- 随机输入下约 是初始段长度的平均估计,不是每段的硬性长度。
- 路归并每次选最小值可用最小堆、胜者树或败者树;更新代价通常为 。
- 磁盘 I/O 计算要区分初始段生成、归并趟数、块容量和是否写回最终结果。
