外部排序

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

外部排序

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

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

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

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

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

置换归并排序:
生成初始归并段
多路归并排序

置换选择排序

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

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

其算法步骤如下:

  1. 初始化
    • 将待排序文件中的前 M 个记录读入 工作区,建立一个 最小堆M工作区 的大小)。
  2. 生成归并段
    • 判断是否有 初始归并段
      • 如果不存在任何 初始归并段 的话,创建一个 初始归并段,并添加 工作区 中的最小元素加入其中。
      • 否则将 工作区 中的元素与上一个 初始归并段 的最大值 MAXV 进行比较。
        • 如果 工作区 中的所有元素都 ≤ MAXV 的话,创建一个新的 初始归并段,并添加 工作区 中的最小元素加入其中。
        • 否则找到第一个 > MAXV 的元素,将其添加到上一个 初始归并段 的末尾。
    • 从输入文件中读取下一个值加入 工作区
ReplacementSelectionstart开始init初始化:读取前M个记录到工作区建立最小堆start->initcheck_segment是否存在初始归并段?init->check_segmentcreate_new创建新的初始归并段添加工作区最小元素check_segment->create_newcompare_maxv工作区所有元素都 ≤ MAXV?check_segment->compare_maxvread_next从输入文件读取下一个值加入工作区create_new->read_nextcreate_new_segment创建新的初始归并段添加工作区最小元素compare_maxv->create_new_segmentfind_greater找到第一个 > MAXV 的元素添加到上一个归并段末尾compare_maxv->find_greatercreate_new_segment->read_nextfind_greater->read_nextcheck_data还有输入数据?read_next->check_datacheck_data->check_segmentend结束check_data->endlabel_heap工作区:最小堆大小为Mlabel_maxvMAXV:上一个归并段的最大值

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

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

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

输入文件 IF
工作区(小根堆)
输出文件 OF1
输出文件 OF2
如果工作区中存在值
> OF1 最大值
否则创建一个
新文件

举一个实际的例子,假设一个输入文件 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} 。

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

输出文件 FO工作区 WA输入文件 FI
————51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
——51, 94, 37, 9214, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
3751, 94, 14, 9263, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 5163, 94, 14, 9215, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 6315, 94, 14, 9299, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 9215, 94, 14, 9948, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 9415, 48, 14, 9956, 23, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 94, 9915, 48, 14, 5623, 60, 31, 17, 43, 8, 90, 166, 100
37, 51, 63, 92, 94, 99#15, 48, 14, 5623, 60, 31, 17, 43, 8, 90, 166, 100
1415, 48, 23, 5660, 31, 17, 43, 8, 90, 166, 100
14, 1560, 48, 23, 5631, 17, 43, 8, 90, 166, 100
14, 15, 2360, 48, 31, 5617, 43, 8, 90, 166, 100
14, 15, 23, 3160, 48, 17, 5643, 8, 90, 166, 100
14, 15, 23, 31, 4860, 43, 17, 568, 90, 166, 100
14, 15, 23, 31, 48, 5660, 43, 17, 890, 166, 100
14, 15, 23, 31, 48, 56, 6090, 43, 17, 8166, 100
14, 15, 23, 31, 48, 56, 60, 90166, 43, 17, 8100
14, 15, 23, 31, 48, 56, 60, 90, 166100, 43, 17, 8——
14, 15, 23, 31, 48, 56, 60, 90, 166#100, 43, 17, 8——
8100, 43, 17——
8, 17100, 43——
8, 17, 43100——
8, 17, 43, 100————
8, 17, 43, 100#————

多路归并

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

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

37
51
63
92
•••
14
15
23
31
•••
8
17
43
100
•••
初始归并段0
8
14
37
输出文件
初始归并段1
初始归并段2
工作区
(小根堆)
选择 最小元素
加入输出文件

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

  1. 初始化
    • 打开所有参与归并的 初始归并段,并读取每个归并段的第一个元素。
    • 将这些元素放入一个数据结构中,以便快速找到最小值(例如,最小堆)。
  2. 归并
    • 从数据结构中取出最小的元素,将其输出到结果文件中。
    • 找到该元素所属的归并段,并从该归并段中读取下一个元素。
    • 将新读取的元素放入数据结构中,并调整数据结构,以保持有序。
    • 重复上述步骤,直到所有归并段都被处理完毕。
  3. 结束
    • 当所有归并段都为空时,归并过程结束,结果文件即为完全有序的文件。

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

MultiWayMergecluster_init1. 初始化阶段cluster_merge2. 归并阶段cluster_end3. 结束阶段cluster_example示例数据结构start开始open_files打开所有初始归并段start->open_filesread_first读取每个归并段的第一个元素open_files->read_firstcreate_heap创建最小堆存储首元素read_first->create_heapcheck_heap检查堆是否为空create_heap->check_heapextract_min从堆中取出最小元素check_heap->extract_minall_empty所有归并段都已处理完毕check_heap->all_empty(堆为空)output_min输出最小元素到结果文件extract_min->output_minfind_segment找到该元素所属的归并段output_min->find_segmentread_next从该归并段读取下一个元素find_segment->read_nextcheck_segment归并段是否为空?read_next->check_segmentcheck_segment->check_heap(该段已空)add_to_heap将新元素加入堆中check_segment->add_to_heapadjust_heap调整堆保持最小堆性质add_to_heap->adjust_heapadjust_heap->check_heapcomplete归并完成结果文件有序all_empty->completeend_node结束complete->end_nodeheap_example最小堆示例:  2 / \5   3segments归并段:S1: [2,8,15...]S2: [3,9,12...]S3: [5,7,11...]result结果文件:[已输出元素...]

继续用上文中通过 置换选择算法 生成的三个 初始归并段 {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, 9914, 15, 23, 31, 48, 56, 60, 90, 1668, 17, 43, 100
51, 63, 92, 94, 9915, 23, 31, 48, 56, 60, 90, 16617, 43, 1008, 14, 37
51, 63, 92, 94, 9915, 23, 31, 48, 56, 60, 90, 16643, 10014, 17, 378
51, 63, 92, 94, 9923, 31, 48, 56, 60, 90, 16643, 10015, 17, 378, 14
51, 63, 92, 94, 9931, 48, 56, 60, 90, 16643, 10017, 23, 378, 14, 15
51, 63, 92, 94, 9931, 48, 56, 60, 90, 16610023, 37, 438, 14, 15, 17
51, 63, 92, 94, 9948, 56, 60, 90, 16610031, 37, 438, 14, 15, 17, 23
51, 63, 92, 94, 9956, 60, 90, 16610037, 43, 488, 14, 15, 17, 23, 31
63, 92, 94, 9956, 60, 90, 16610043, 48, 518, 14, 15, 17, 23, 31, 37
63, 92, 94, 9956, 60, 90, 16648, 51, 1008, 14, 15, 17, 23, 31, 37, 43
63, 92, 94, 9960, 90, 16651, 56, 1008, 14, 15, 17, 23, 31, 37, 43, 48
92, 94, 9960, 90, 16656, 63, 1008, 14, 15, 17, 23, 31, 37, 43, 48, 51
92, 94, 9990, 16660, 63, 1008, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56
92, 94, 9916663, 90, 1008, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60
94, 9916690, 92, 1008, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63
94, 9992, 100, 1668, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90
9994, 100, 1668, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92
99, 100, 1668, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92, 94
8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92, 94, 99, 100, 166

胜者树

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

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

树形结构优化(胜者树/败者树)优化的目的就是优化这个过程:

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


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

8
9
8
9
15
8
17
10
9
20
15
8
9
90
17
15
16
20
38
20
30
25
28
15
50
11
16
95
99
18
20

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

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

败者树

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

9
15
17
10
20
9
90
10
9
20
15
8
9
90
17
15
16
20
38
20
30
25
28
15
50
11
16
95
99
18
20
8
9
15
9
8
17
8
8
胜者需要进行下一轮比较

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

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

补充

胜者树更加直观,败者树的优势在哪?

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

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

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