外部排序

⭐ 中优先级

其实外部排序不是高频考点，但是遭不住 23 年考了一道置换选择排序的大题，所以还是得掌握下 外部排序的过程 。这也给了我们一个启示：涉及到算法过程的知识点，都要留一个心眼，也许之前不考察但是今年就冷不丁地来一道大题。

外部排序

当待排序的数据量大到无法一次性全部装入内存时，就必须采用 外部排序 。外部排序的基本思路是：先将整个数据集划分成若干能够装入内存的子块，对每个子块在内存中完成内部排序；随后再把这些已排序的子块逐步合并，最终得到整体有序的结果。这样既克服了内存容量的限制，又能高效地对海量数据完成排序。

外部排序的整体过程通常可以划分为两个关键阶段：

1. 生成初始归并段
   先采用 置换选择排序 对原始的无序文件进行扫描。置换选择能够在一次扫描中尽可能长地生成有序子文件，这些子文件即称为 初始归并段 。每个归并段都是内部有序的，且长度尽量大，以减少后续合并的轮数。

2. 多路归并
   将所有 初始归并段 以多路归并的方式逐步合并。每一次归并都会把若干归并段合并成一个更长的有序段，重复此过程直至只剩下一个完整的有序文件，从而得到最终的排序结果。

通过上述两步，外部排序能够在 磁盘与内存之间 高效地完成大规模数据的排序。

置换归并排序：

置换选择排序

置换选择排序 （Replacement Selection Sort）是 外部排序 的一个步骤，用于生成 初始归并段 ，其核心功能是在 内存缓冲区 有限的情况下，尽可能地生成较长的 初始归并段 。

置换选择排序 通过维护一个 工作区 来实现这一目标，工作区是一个 小根堆 。

其算法步骤如下：

1. 初始化 ：

• 将待排序文件中的前 M 个记录读入 工作区 ，建立一个 最小堆 （M 为 工作区 的大小）。

  2. 生成归并段 ：

• 判断是否有 初始归并段

  • 如果不存在任何 初始归并段 的话，创建一个 初始归并段 ，并添加 工作区 中的最小元素加入其中。
  • 否则将 工作区 中的元素与上一个 初始归并段 的最大值 MAXV 进行比较。
    • 如果 工作区 中的所有元素都 ≤ MAXV 的话，创建一个新的 初始归并段 ，并添加 工作区 中的最小元素加入其中。
    • 否则找到第一个 > MAXV 的元素，将其添加到上一个 初始归并段 的末尾。

• 从输入文件中读取下一个值加入 工作区 。

置换选择排序 核心思想 的如下：

• 判断工作区 ：如果工作区中所有记录的键值都小于当前输出文件（即已生成的有序段）中最后一个记录的键值，则需要新建一个输出文件 ，并将这些记录写入该文件，开启新的有序段。
• 继续合并 ：如果工作区中存在键值不小于当前输出文件末尾记录的记录，则 不断将这些记录追加到已有的输出文件 中。这样可以确保输出文件始终保持递增有序，从而形成一个完整的有序序列。

通过上述两步的交替执行，置换选择排序能够在外部存储环境下有效地生成有序文件，适用于大型数据集的排序任务。

举一个实际的例子，假设一个输入文件 FI 的内容为 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100。

我们可以通过 置换选择排序 生成 3 个 初始归并段 ，分别为 {37, 51, 63, 92, 94, 99} ，{14, 15, 23, 31, 48, 56, 60, 90, 166} ，{8, 17, 43, 100} 。

算法执行的过程如下表所示：

多路归并

多路归并 的目标是将多个已经排序的 初始归并段 （子文件）合并成一个更大的有序文件。

其核心思想是从若干 归并段 中每次选取一个最小的元素加入 工作区 （小根堆 ），然后从 工作区 中选取最小的元素添加到 输出文件 中，通过这种方式可以保证每次添加到 输出文件 中的值是当前的最小值。

多路归并 的具体过程如下：

1. 初始化 ：

• 打开所有参与归并的 初始归并段 ，并读取每个归并段的第一个元素。
• 将这些元素放入一个数据结构中，以便快速找到最小值（例如，最小堆 ）。

2. 归并 ：

• 从数据结构中取出最小的元素，将其输出到结果文件中。
• 找到该元素所属的归并段，并从该归并段中读取下一个元素。
• 将新读取的元素放入数据结构中，并调整数据结构，以保持有序。
• 重复上述步骤，直到所有归并段都被处理完毕。

3. 结束 ：

• 当所有归并段都为空时，归并过程结束，结果文件即为完全有序的文件。

多路归并的过程可以通过以下流程图理解：

继续用上文中通过 置换选择算法 生成的三个 初始归并段 {37, 51, 63, 92, 94, 99} ，{14, 15, 23, 31, 48, 56, 60, 90, 166} ，{8, 17, 43, 100} 作为例子。对于这三个 初始归并段 ，多路归并 的过程如下（假设采用三路归并的话）：

最佳归并树（哈夫曼树思想）

对于长度分别为 $m, n$ 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 $m+n-1$ 次。故最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据 哈夫曼树（最佳归并树） 思想的启发，可采用如图所示的最佳合并顺序。

上图中的 6 个序列的合并过程为：

1. 第 1 次合并：表 A（10）与表 B（35）合并，生成含 45 个元素的表 AB（最多比较 $10+35-1=44$ 次）
2. 第 2 次合并：表 AB（45）与表 C（40）合并，生成含 85 个元素的表 ABC（最多比较 $45+40-1=84$ 次）
3. 第 3 次合并：表 D（50）与表 E（60）合并，生成含 110 个元素的表 DE（最多比较 $50+60-1=109$ 次）
4. 第 4 次合并：表 ABC（85）与表 DE（110）合并，生成含 195 个元素的表 ABCDE（最多比较 $85+110-1=194$ 次）
5. 第 5 次合并：表 ABCDE（195）与表 F（200）合并，生成含 395 个元素的最终表（最多比较 $195+200-1=394$ 次）

最坏情况下的比较总次数为：$44+84+109+194+394=825$。

核心思想：每次选择当前长度最小的两个有序表进行合并（类似哈夫曼树的构造过程），可使最坏情况下的总比较次数最小化。

胜者树

在进行 k 路归并（如外排序）时，我们需要从多个有序子序列中 快速找出当前最小元素 ，然后将其输出并替换为该序列的下一个元素。

最简单的做法就是每次遍历序列头部元素，找到最小值。该方法的时间复杂度为 O(k) ，效率比较低，尤其是当 k 比较大 时。

树形结构优化（胜者树 /败者树 ）优化的目的就是优化这个过程：

用一棵完全二叉树维护每一轮比较的结果，使得我们可以在 O(logk) 时间内完成最小值查找与更新。

胜者树 可以理解为 胜者晋级的淘汰赛模型 ：类比体育比赛的淘汰制，每一轮两个选手进行比较，胜者晋级上一轮，最终全局胜者抵达根节点。

在 胜者树 中，每个 内部结点 记录的是该轮比较的 胜者 （较小的元素），而 叶子节点 表示每个输入归并段的当前值。因此，整棵树的 根节点 就表示 全局最小值 。

当某个归并段输出了最小值并更新为下一个元素时，需要 从该叶子节点向上，逐层与兄弟节点重新比较，构建新的胜者路径 ，最终将新的最小值更新到根节点。

败者树

败者树 可以理解为 败者记录的升降赛模型 ：类比体育比赛中每场比赛将败者淘汰出局但保留记录，胜者则继续晋级下一轮，最终全局胜者脱颖而出，但 不会被记录在树中，而是单独保留 ，以便快速访问。

在 败者树 中，每个 内部结点 记录的是该轮比较的 败者 （较大的元素），而 叶子节点 同样表示每个输入归并段的当前值。最终的全局胜者（最小值） 不保存在树中，而是单独保存在一个外部变量中 。

当某个归并段输出了最小值并更新为下一个元素时，需要 从该叶子节点出发，沿着路径向上与路径上的败者重新比较，并在每一层更新败者信息 。

补充

胜者树更加直观，败者树的优势在哪？

在用 胜者树 的时候，每个新元素上升时，首先先和兄弟结点比较，然后再更新父结点（访存 2 次）。

在使用 败者树 的时候，每个新元素上升时，只需要获得父节点并比较即可（访存 1 次）。

所以总的来说， 减少了访存的时间 ，进而 提高了程序运行的效率 。

相关笔记

• 数组查找
• 散列表查找
• 查找概述
• 排序概述
• 树形查找