考研笔记

置换-选择排序与最佳归并树

这两节是「减少归并段个数 」这条路线的两步——8.7.3 的败者树 走的是另一条路（增大归并路数 ）。

  • 置换-选择排序：让初始归并段变长，从而变少。
  • 最佳归并树：归并段长度不等时，安排归并顺序使 I/O 次数最少。

两节都是纯手算，且都能算出一个确定的数字，所以特别适合出计算题。

机制

为什么需要置换-选择

由 8.7.2 可知，减少初始归并段个数 也可以减少归并趟数 。若总的记录个数为 ，每个归并段的长度为 ，则归并段的个数 。

采用内部排序算法得到的各个初始归并段长度都相同（除最后一段外），它依赖于内部排序时可用内存工作区的大小。 因此，必须探索新的方法，用来产生更长的初始归并段——这就是置换-选择算法。

置换-选择算法

设初始待排文件为 FI，初始归并段输出文件为 FO，内存工作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 个记录。

  1. 从 FI 输入 个记录到工作区 WA。
  2. 从 WA 中选出其中关键字取最小值的记录，记为 MINIMAX 记录。
  3. 将 MINIMAX 记录输出到 FO 中去。
  4. 若 FI 不空，则从 FI 输入下一个记录到 WA 中。
  5. 从 WA 中所有关键字比 MINIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX 记录。
  6. 重复 3)~5)，直至在 WA 中选不出新的 MINIMAX 记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到 FO 中去。
  7. 重复 2)~6)，直至 WA 为空。由此得到全部初始归并段。

教材的例子（表 8.2）：，WA 容量为 3。

输出文件 FO工作区 WA输入文件 FI
——17, 21, 05, 44, 10, 12, 56, 32, 29
—17 21 0544, 10, 12, 56, 32, 29
0517 21 4410, 12, 56, 32, 29
05 1710 21 4412, 56, 32, 29
05 17 2110 12 4456, 32, 29
05 17 21 4410 12 5632, 29
05 17 21 44 5610 12 3229
05 17 21 44 56 #10 12 3229
1029 12 32—
10 1229   32—
10 12 2932—
10 12 29 32——
10 12 29 32 #——

结果：两个初始归并段 （长度 5）和 （长度 4）。

边界辨析：

WA 只能装 3 个记录，却产出了长度为 5 的归并段——这正是置换-选择的全部价值： 归并段的长度不再受内存工作区大小的限制。 关键在第 5 步的「比 MINIMAX 大」这个条件：新读进来的记录只要比刚输出的那个大， 就还能接在当前归并段后面；比它小的只能留给下一段（表中被划掉的 10、12、32 就是这样攒出第二段的）。

教材末尾还有一句：「在 WA 中选择 MINIMAX 记录的过程需利用败者树来实现。」 ——败者树 在这里第二次出现，用途从「归并选最小」变成「工作区选 MINIMAX」。

最佳归并树

文件经过置换-选择排序后，得到的是长度不等的初始归并段。如何组织长度不等的初始归并段的归并顺序，使得 I/O 次数最少？

在归并树中，各叶结点表示一个初始归并段，上面的权值表示该归并段的长度；叶结点到根的路径长度表示其参加归并的趟数；各非叶结点代表归并成的新归并段；根结点表示最终生成的归并段。树的带权路径长度 WPL 为归并过程中的总读记录数，所以 I/O 次数 。

教材的例子：由置换-选择排序得到 9 个初始归并段，长度依次为 ，做 3 路平衡归并。

方案内部结点（新归并段长度）WPLI/O 次数
图 8.18 任意 3 路平衡归并242484
图 8.19 最佳归并树223446

「显然，归并方案不同，所得归并树不同，树的带权路径长度（I/O 次数）亦不同。为了优化归并树的 WPL，可以将哈夫曼树的思想推广到 叉树的情形，在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的 I/O 次数最少的最佳归并树。」

虚段：不足以构成严格 叉树时

图 8.19 中的哈夫曼树是一棵严格 3 叉树，即树中只有度为 3 或 0 的结点。

若只有 8 个初始归并段（上例中少了一个长度为 30 的归并段）：

  • 错误做法：缺额的归并段留在最后，即除最后一次做二路归并外，其他各次归并仍是 3 路归并——此归并方案的 I/O 次数为 386。「显然，这不是最佳方案。」
  • 正确的做法：若初始归并段不足以构成一棵严格 叉树（也称正则 叉树）时，则需添加长度为 0 的「虚段」，按照哈夫曼树的原则，权为 0 的叶子应离树根最远。此时的 I/O 次数仅为 326。

添加虚段数目的判定（设度为 0 的结点有 个，度为 的结点有 个，归并树的结点总数为 ）：

总结点数度为的结点数度为的结点数 总结点数所有结点的度数之和

因此，对严格 叉树有 ，由此可得

  • 若 ，则说明这 个叶结点（初始归并段）正好可以构造 叉归并树。此时内结点有 个。
  • 若 ，则说明对于这 个叶结点，其中有 个多余，不能包含在 叉归并树中。为构造包含所有 个初始归并段的 叉归并树，应在原有 个内结点的基础上再增加 1 个内结点，并补充 个虚段。

验算教材例子：，。，故补 个虚段。补后 ， ✅。图 8.20 中最深一层正是 三个叶子。

层次辨析：

这里的「三式」与 5.1.3 的三式联立是同一套东西： 总结点数 = 各度结点数之和；总结点数 = 总分支数 + 1。 区别只是这里限定了「严格 叉」，即 ，于是两式就能解出 。 第 5 章的公式在第 8 章直接兑现，不必当成新知识。

手算模板

置换-选择排序：

  1. 画三列表：FO | WA | FI。
  2. 先读 个进 WA。
  3. 每轮：在 WA 中「比上一个输出值大」的记录里选最小，输出到 FO；从 FI 补一个进 WA。
  4. 若 WA 中没有比上一个输出值大的记录了 → 当前归并段结束，写 #，然后从 WA 全体里重新选最小开始新段。
  5. FI 空后继续排空 WA。

最佳归并树：

  1. 数初始归并段个数 和路数 。
  2. 算 ： 不补； 补 个长度为 0 的虚段。
  3. 按哈夫曼树的方法建 叉树：每次取最小的 个合并，新结点权 = 之和。虚段（权 0）自然会落在最深处。
  4. 所有内部结点的权值。
  5. 次数。

边界

说法判断说明
「初始归并段长度不能超过内存工作区」❌置换-选择可以产生更长的归并段（例中 WA=3 却得到长度 5）
「置换-选择每段长度相同」❌长度不等，这正是需要最佳归并树的原因
「MINIMAX 是 WA 中的最小值」⚠️是比上一个输出值大的记录中的最小值；只有段首才是全体最小
「置换-选择用堆实现」⚠️教材原话是**「需利用败者树来实现」**
「I/O 次数 = WPL」❌（一读一写）
「WPL 要加上叶结点的权」❌WPL 内部结点的权值（等价于 ）
「归并段不够时最后做一次少路归并即可」❌不是最佳方案（例中 386 > 326）
「虚段数 」❌是 ，
「虚段可以放在任意位置」❌权为 0 的叶子应离树根最远
「最佳归并树是普通哈夫曼树」⚠️是推广到 叉的严格（正则） 叉哈夫曼树

口径差异：

置换-选择和最佳归并树在算法竞赛里完全没有对应物，它们解决的是「磁盘慢、内存小」这个 1970 年代的问题。 但 408 年年在考：置换-选择生成初始归并段的实例（2023）、构造三叉哈夫曼树及相关的分析和计算（2013）。 这一节的好处是答案唯一且可验算——I/O 次数是个确定的整数，算完可以用 内部结点 复核。

对照速查

量式子
严格 叉树，
判虚段； 时补 个
WPL 所有内部结点的权值
I/O 次数
教材例子段数方案I/O
9任意 3 路平衡归并484
同上9最佳归并树446
去掉 308缺额留最后做二路386
同上8 + 1 虚段最佳归并树326
减少 I/O 的两条路对应节
增大归并路数 8.7.3 败者树
减少归并段个数 8.7.4 置换-选择
段长不等时安排顺序8.7.5 最佳归并树

考点

  • 置换-选择排序生成初始归并段的实例（2023 命题追踪）——画三列表。
  • MINIMAX 的选取条件（比上一个输出值大的最小者）。
  • 构造三叉哈夫曼树及相关的分析和计算（2013 命题追踪）。
  • 虚段数目的判定公式。
  • I/O 次数 。
  • 权为 0 的虚段应离根最远。
  • 「缺额留最后做低路归并」不是最佳方案。

链接

反向链接