掌握外部排序的初始归并段生成和多路归并流程,模拟置换选择排序,并理解败者树、归并路数与磁盘 I/O 次数的关系。

# 一、外部排序的基本流程

当全部待排序记录无法同时装入内存时,需要借助外存完成排序。外部排序主要受磁盘块读写次数影响,而不是只比较 CPU 内部的关键字比较次数。典型流程分为:

  1. 生成初始归并段:把数据分批读入内存,生成各自有序的子文件。
  2. 多路归并:每次把 kk 个有序段合并为一个更长的有序段,反复进行直到只剩一个段。

flowchart LR
    A[外存无序文件] --> B[生成若干有序初始段]
    B --> C[多路归并一趟]
    C --> D{是否只剩一个有序段}
    D -->|否| C
    D -->|是| E[得到完整有序文件]

若一趟读入并写出整个文件,文件含 NN 个记录、每个磁盘块含 BB 个记录,则一次归并趟约需读写 2⌈N/B⌉2\lceil N/B\rceil 个块传送;归并趟数直接影响总 I/O。

# 二、置换选择排序生成初始段

置换选择排序(Replacement Selection)使用容量为 MM 的内存工作区,边输出当前归并段、边读入新记录。其核心是尽量让新读入的记录继续进入当前有序段。

  1. 把输入文件开头的 MM 个记录放入工作区,按关键字组织为最小堆。
  2. 取出并输出堆顶最小记录,记当前归并段最后输出值为 lastlast。
  3. 从输入文件读入一个新记录 xx:
    • 若 x≥lastx\ge last,它仍可加入当前归并段;
    • 若 x<lastx<last,它不能放在当前段末尾,冻结到下一归并段。
  4. 在活动记录中继续输出最小者;当前活动集合为空时结束本段,启用冻结记录开始下一段。
  5. 重复直至输入和工作区均处理完。

对随机输入,一个初始归并段的平均长度约为 2M2M,通常比 “每次只把 MM 条记录装入内存、内部排序后输出一段” 的长度更大;具体长度随输入次序变化,并不保证一定达到 2M2M。

例题 8.1:置换选择的冻结判断

工作区容量为 33,当前归并段最后输出的关键字为 2020。新读入 2727 时,它仍可加入当前段;新读入 1212 时,它小于 2020,必须冻结到下一段。冻结记录仍保留在工作区,但暂不参加当前段的最小值选择。

# 三、多路归并

设有 rr 个初始归并段。kk 路归并每次从 kk 个段各读取一个当前记录,取其中最小值输出,再从该记录所属段补入下一个记录。

  • 直接逐个比较 kk 个当前记录,每输出一个记录需 O(k)O(k) 次比较。
  • 用最小堆或胜者树 / 败者树维护当前候选值,每次输出和更新通常需 O(log⁡k)O(\log k) 次比较。
  • 归并树的叶子对应输入归并段,根位置的胜者代表当前全局最小值。

败者树在内部结点保存比较中落败的一方,当前最小者单独作为胜者保存。某一输入段读入新记录后,只需沿它到根的路径逐层重赛,调整代价为 O(log⁡k)O(\log k)。胜者树、败者树都是多路归并的选择树实现。

多路归并需要为每个输入段准备缓冲区,并为输出准备缓冲区,因此可用路数受内存中可容纳的输入、输出缓冲块数限制。增大 kk 可减少归并趟数,但需要更多输入缓冲空间。

# 四、归并趟数与 I/O

若每趟最多合并 kk 个归并段,初始有 rr 个归并段,理想情况下归并趟数约为

p=⌈log⁡kr⌉.p=\lceil\log_k r\rceil.

实际分组需满足每个归并段在每趟恰好参与一次合并,尾组不足 kk 段时也要按规则处理。若每趟都读取并写出全文件,则总块传送次数约为

2⌈NB⌉p,2\left\lceil\frac{N}{B}\right\rceil p,

尚未计入初始段生成阶段的读写,也未考虑最后一趟直接输出而省略写回等实现差异。分析题要明确题目问的是归并趟数、磁盘读写次数还是块传送次数。

# 五、考场检查清单

  1. 外部排序先形成有序初始段,再做多路归并。
  2. 置换选择中,新记录不小于当前段最后输出值时可留在当前段;较小时冻结到下一段。
  3. 随机输入下约 2M2M 是初始段长度的平均估计,不是每段的硬性长度。
  4. kk 路归并每次选最小值可用最小堆、胜者树或败者树;更新代价通常为 O(log⁡k)O(\log k)。
  5. 磁盘 I/O 计算要区分初始段生成、归并趟数、块容量和是否写回最终结果。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝