- 一、多路归并
- 二、败者树
- 三、置换-选择排序
- 四、最佳归并树
一、多路归并
1. 基本概念
多路归并是外部排序第二阶段的核心操作。它将多个已经排序好的序列（称为“归并段”或“顺串”）合并成一个更大的有序序列。这里的“路”（K）指的是同时进行合并的归并段数量。
2. 为什么需要多路归并？
- 减少归并轮数：这是最根本的原因。归并轮数 \(S = \lceil \log_K N \rceil\)，其中 \(N\) 是初始归并段的数量。增大 K 可以显著减少 S。
- 例子：有 100 个初始归并段。
- 二路归并（K=2）：需要 \(\lceil \log_2 100 \rceil = 7\) 轮归并。
- 十路归并（K=10）：需要 \(\lceil \log_{10} 100 \rceil = 2\) 轮归并。
- 归并轮数减少，意味着磁盘 I/O 次数大大降低，从而提升了整体排序效率。
- 例子：有 100 个初始归并段。
3. 工作原理
- 初始化：为 K 个归并段分别开设一个输入缓冲区，并从每个归并段中读入一部分数据到对应的缓冲区。
- 选择最小元：从 K 个缓冲区的当前元素中，选出最小的那个元素。
- 输出：将选出的最小元素输出到最终结果文件（或下一个临时文件）中。
- 补充数据：从刚刚输出元素所在的归并段中，读取下一个元素到其缓冲区。如果该归并段已读完，则忽略该路。
- 重复：重复步骤 2-4，直到所有 K 个归并段的所有数据都被处理完毕。
4. 核心挑战与解决方案
- 挑战：在步骤 2 中，如何高效地从 K 个元素中找出最小值？如果使用简单的顺序比较，每次需要 K-1 次比较，当 K 很大时，CPU 开销会变得很大。
- 解决方案：使用 败者树。它可以将每次选择最小元的比较次数降低到 O(log K)。
二、败者树
1. 基本概念
败者树是完全二叉树，它是多路归并中用于高效选择最小元（或最大元）的数据结构。它是锦标赛排序思想的延伸。
2. 为什么需要败者树？
为了解决多路归并中顺序比较效率低下的问题。它通过树形结构记录比较结果，使得每次选出最小元后，重新调整树的代价很小。
3. 工作原理
我们以最小败者树为例（用于选出最小值）：
- 叶子节点：存放 K 路归并段当前参与比较的元素。
- 内部节点：存放的是其子节点之间比较的 “败者”（即较大的那个）。而 “胜者”（较小的那个）则继续向上比较。
- 根节点之上：有一个额外的节点，用于存放最终的 “胜者”（即全局最小元）。
工作流程分为初始化和调整两步：
-
初始化：
- 将 K 路元素的第一个值放入叶子节点。
- 从底向上，两两比较，将败者（大值）记录在父节点中，胜者（小值）继续向上比较。
- 最终，树顶的“胜者”就是当前 K 个元素中的最小值。
-
调整：
- 当我们输出这个最小值后，需要从该最小值所在的归并段中读取下一个元素，替换掉对应的叶子节点。
- 然后，沿着从该叶子节点到根节点的路径，重新进行比赛。
- 比较只在兄弟节点之间进行，新的败者留在父节点，胜者继续向上。
- 这个过程只需要 \(\lceil \log_2 K \rceil\) 次比较。
4. 优势
- 效率高：初始化需要 K-1 次比较，但之后每次调整（即每次选出一个最小元）仅需 \(\lceil \log_2 K \rceil\) 次比较，与 K 的大小无关。
- 稳定：比较次数不随 K 的增大而线性增长，使得采用非常大的 K 值进行归并成为可能。
三、置换-选择排序
1. 基本概念
置换-选择排序用于外部排序的第一阶段，即生成初始归并段。它的目标是突破内存工作区大小的限制，生成长度大于内存容量的初始归并段。
2. 为什么需要置换-选择排序？
传统方法生成的归并段大小 ≈ 内存工作区大小。如果归并段数量 N 减少，根据公式 \(S = \lceil \log_K N \rceil\)，归并轮数 S 也会减少。置换-选择排序正是通过生成更少、更长的归并段来提升整体效率。
3. 工作原理
假设内存工作区大小为 w。
- 初始化：从输入文件中读入
w个记录到内存工作区。 - 创建归并段：
a. 从工作区中选出最小的记录（记为MIN），将其输出到当前归并段。
b. 从输入文件中读入下一个记录。
c. 关键判断：
- 如果新读入的记录 大于或等于 刚输出的MIN，那么它可以被纳入 当前 归并段。将其填入刚才MIN空出的位置。
- 如果新读入的记录 小于 刚输出的MIN，那么它不能被纳入当前归并段（否则会破坏有序性）。它只能被纳入 下一个 归并段。此时，我们将其放在一边，并缩小有效工作区范围。
d. 从 当前有效的 工作区中再次选出最小记录作为新的MIN，重复输出和替换过程。 - 结束当前归并段：当工作区中不再有任何大于等于上一个输出
MIN的记录时（即所有记录都只能留给下一个归并段），当前归并段结束。 - 开始新归并段：将之前为下一个归并段“囤积”的记录重新纳入有效工作区，开始生成下一个归并段。
- 重复：直到所有输入记录处理完毕。
4. 效果
- 生成的初始归并段的平均长度是 2w。
- 归并段数量减少，从而优化了后续的归并过程。
四、最佳归并树
1. 基本概念
最佳归并树解决了当前初始归并段长度不相等时，如何组织多路归并的顺序，使得总的 I/O 次数最少的问题。它的本质是 K 叉哈夫曼树。
2. 为什么需要最佳归并树？
- 使用置换-选择排序后，初始归并段的长度各不相同。
- 如果随意进行归并，可能会将大的归并段过早地参与合并，导致“笨重的”数据被反复读写，增加 I/O 负担。
- 最佳归并树通过 “让短的段先合并，长的段后合并” 的策略，使带权路径长度最短，即总 I/O 次数最少。
3. 构建过程（以 K 路归并为例）
- 构造虚拟归并段：如果初始归并段数量
N无法直接构成一棵严格的 K 叉树（即(N-1) % (K-1) != 0），需要补充(K-1) - (N-1) % (K-1)个长度为 0 的 虚段。这是为了确保在归并过程中，每次都是合并 K 个段，避免最后轮次合并的段数不足，造成浪费。 - 构建 K 叉哈夫曼树：
- 将所有归并段（包括虚段）视为叶子节点，其权重就是归并段的长度（记录数或字节数）。
- 每次从集合中选择 K 个权重最小 的节点。
- 将它们合并，生成一个新的父节点，该父节点的权重为这 K 个子节点权重之和。
- 将这个新的父节点放回集合中。
- 重复上述过程，直到集合中只剩下一个节点（根节点）。这棵树就是最佳归并树。
4. 如何指导归并？
这棵最佳归并树就指明了最优的归并顺序。从叶子节点开始，按照树的层次进行归并。父节点的权重就是合并这 K 个段所需进行的 I/O 次数（读入这 K 个段 + 写出合并后的段）。根节点的权重就是整个归并过程的总 I/O 代价。
5. 目标
最小化总的归并代价，即 最小化带权路径长度（WPL），从而最大限度地减少磁盘读写次数。