题目

对含有 n（n > 0）个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作区，工作区中能保存 m 个记录，请回答下列问题：

(1) 如果文件中有 19 个记录，其关键字是 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100；当 m = 4 时，可以生成几个初始归并段，各是什么？

(2) 对任意的 m（n > m > 0），生成的第一个初始归并段的长度最大值和最小值分别是多少？

解析

算法回顾：置换-选择排序的 4 条规则

编者注（生僻术语）：「置换-选择排序」是外部排序中生成初始归并段的算法（不是排序算法本体），目的是让每个初始归并段比工作区还长——平均长度可达 2m，从而减少归并趟数。务必和"内部排序的选择排序"区分开。

工作区容量 m 个记录，记当前段已输出的最大值为 last_out（每段开始时重置为 −∞）。每一轮：

1. 从工作区未冻结部分挑出 ≥ last_out 的最小者，输出到当前归并段，更新 last_out；
2. 从输入读 1 个新记录补进工作区：
   • 新记录 ≥ last_out → 进入"未冻结"，可参与本段后续选择；
   • 新记录 < last_out → 冻结，留给下一段；
3. 当工作区全部冻结或输入也读完且工作区空时，当前段关闭、解冻所有记录、last_out 重置，开始下一段。

(1) m = 4 时的归并段

答案：共 3 个初始归并段：

• R1 = (37, 51, 63, 92, 94, 99)，长度 6
• R2 = (14, 15, 23, 31, 48, 56, 60, 90, 166)，长度 9
• R3 = (8, 17, 43, 100)，长度 4

下表逐轮模拟（粗体=本轮选中输出，× 表示冻结）：

#	工作区状态（前）	输出→段	读入 / 处理
0	（空）→ 读 51,94,37,92	—	初始装入
1	{51, 94, 37, 92}	37 → R1	读 14；14<37 冻
2	{51, 94, 14×, 92}	51 → R1	读 63；63≥51
3	{63, 94, 14×, 92}	63 → R1	读 15；15<63 冻
4	{15×, 94, 14×, 92}	92 → R1	读 99；99≥92
5	{15×, 94, 14×, 99}	94 → R1	读 48；48<94 冻
6	{15×, 48×, 14×, 99}	99 → R1	读 56；56<99 冻
R1 闭	工作区全冻结 → 解冻为 {15,48,14,56}，last_out 重置
7	{15, 48, 14, 56}	14 → R2	读 23
8	{15, 48, 23, 56}	15 → R2	读 60
9	{60, 48, 23, 56}	23 → R2	读 31
10	{60, 48, 31, 56}	31 → R2	读 17；17<31 冻
11	{60, 48, 17×, 56}	48 → R2	读 43；43<48 冻
12	{60, 43×, 17×, 56}	56 → R2	读 8；8<56 冻
13	{60, 43×, 17×, 8×}	60 → R2	读 90
14	{90, 43×, 17×, 8×}	90 → R2	读 166
15	{166, 43×, 17×, 8×}	166 → R2	读 100；100<166 冻
R2 闭	工作区全冻结 + 输入空 → 解冻为 {100,43,17,8}，last_out 重置
16	{100, 43, 17, 8}	8 → R3	（无输入）
17	{100, 43, 17}	17 → R3
18	{100, 43}	43 → R3
19	{100}	100 → R3
R3 闭	工作区空 + 输入空

合计 6 + 9 + 4 = 19 个记录，全部输出完毕 ✓

(2) 第一个初始归并段长度的最大值与最小值

答案：最大值 = n；最小值 = m。

最大值 n（输入恰好升序时取到）：每次读入的新记录都 ≥ last_out，永远不会被冻结，所有 n 个记录都进入 R1。

最小值 m（输入恰好降序时取到）：

• 初始读入工作区的 m 个就是输入的最大 m 个；
• 输出工作区最小（即第 m 大），读入下一个，新读入比刚才输出的还小 → 冻结；
• 再输出工作区次小，读下一个，仍比刚才输出小 → 冻结；
• ……如此进行 m 轮后，工作区全部冻结，R1 关闭。R1 长度 = m。

直觉：置换-选择的"威力"在于"还没冻结的记录"可以多写入当前段。如果输入是单调递减的，每个新读入都立刻冻结，整段就退化成一次"对工作区里的 m 个记录排序输出"，长度恰好等于 m。

编者注（生僻术语）：教材常说置换-选择能产生平均长度 2m 的初始归并段（Knuth 1973 年证明）——介于本题最大 n 和最小 m 之间。本题不要求记 2m 这个结论，但理解了"为什么是 m..n 区间"自然就理解了为什么平均比 m 长。