外部排序

外部排序

当待排序的数据量非常大，以至于无法一次性全部加载到内存中时，就需要使用外部排序。

外部排序通常分为两个主要阶段：

• 初始归并段生成： 使用置换选择排序，根据原始无序文件生成若干个尽量长的的有序文件，这些有序文件叫做初始归并段。
• 多路归并： 将这些初始归并段逐步合并，最终得到完全有序的文件。

置换选择排序

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

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

其算法步骤如下：

1. 初始化：
   • 将待排序文件中的前 M 个记录读入工作区，建立一个最小堆（M 为工作区的大小）。
2. 生成归并段：
   • 判断是否有初始归并段
     • 如果不存在任何初始归并段的话，创建一个初始归并段，并添加工作区中的最小元素加入其中。
     • 否则将工作区中的元素与上一个初始归并段的最大值 MAXV 进行比较。
       • 如果工作区中的所有元素都 ≤ MAXV 的话，创建一个新的初始归并段，并添加工作区中的最小元素加入其中。
       • 否则找到第一个 > MAV 的元素，将其添加到上一个初始归并段的末尾。
   • 从输入文件中读取下一个值加入工作区。

举一个实际的例子，假设一个输入文件 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} 作为例子。 对于这三个初始归并段，多路归并的过程如下（假设采用三路归并的话）：

胜者树败者树

在进行 k 路归并的过程中，我们需要从 k 个有序文件的当前值中筛选出来一个最小值加入输出文件中。 这里最简单的方式就是一次遍历，当然也可以使用胜者树，如下图所示，两者的时间复杂度都为 O(k)。

简而言之，胜者树（winner tree）就是通过树形结构将最小值不断向根结点传递。

败者树与胜者树不同，它在每次比较中将较大的元素（败者）向上传递并保存在中间结点中，胜者则继续与其他胜者进行下一轮的比较。最终的全局胜者（最小值）不会存储在树中，而是单独保存在树外或根节点位置，供快速访问。

对于胜者树败者树，了解两者的基本概念即可。具体来说，两者对比如下：