【数据结构】外部排序、败者树

1. 外部排序

1. 外存、内存之间的数据交换

操作系统以“块”为单位对磁盘存储空间进行管理。如：每块大小 1KB，各个磁盘块内存放着各种各样的数据。

磁盘的读/写以块为单位，数据读入内存后才能被修改，修改完还要写会磁盘。

2. 外部排序原理

外部排序：数据元素太多，无法一次全部读入内存进行排序。

使用“归并排序”的方法，最少只需在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序。

3. 过程步骤

1）构建初始“归并段”

“归并排序”要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘。

说明：将磁盘8个块中每个块内元素有序排序。生成4个初始归并段。

构造初始归并段：需要8次“读”和8次“写”。

2）第一趟归并

将8个初始归并段划分成4个归并段，重新两两归并。 注意：归并段1中的数据要放在输入缓冲区1中，如果某个输入缓冲区内归并完成了没有数据，则要将对应的归并段中的数据整块放入。

3）第二趟归并

将最终的两个归并段再次归并。 注意：归并段1中的数据要放在输入缓冲区1中，如果某个输入缓冲区内归并完成了没有数据，则要将对应的归并段中的数据整块放入。

说明：经过两趟归并。从每个块来看，块内的元素是有序的，从整体来看，整个磁盘中的数据也是有序的。

这里由于归并块不多，只用了两趟归并。具体视情况而定。

4. 时间开销分析

外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间。

读、写磁盘次数=16+16*2=48次

16表示文件总快数*2。2表示归并趟数。

注：磁盘是慢速设备，读写次数太对会导致时间开销大幅增加。

5. 优化思路

思路一：

多路归并。比如上面例子使用4路归并，则只要一趟即可。

读、写磁盘次数=16+16*1=32次。

重要结论：采用多路归并可以减少归并趟数，从而减少磁盘I/O（读写）次数。

多路归并的负面影响：

1. k路归并时，需要开辟k个输入缓冲区，内存开销增加。
2. 每挑选一个关键字需要对比关键字(k-1)次，内部归并所需时间增加。

思路二：

减少归并段数量，即增加初始归并段的长度。

2. 败者树

1. 什么是败者树

败者树：可视为一棵完全二叉树(多了一个头头)。k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往，上继续进行比较，一直到根结点。

2. 败者树的构造

若有8位参赛者，则构造败者树需要7次比拼。

3. 败者树的应用

如果有新的元素加入，基于已经构建好的败者树，选出新的胜者只需进行3场比赛。而并不需要7场比赛。

4. 败者树在多路平衡归并中的应用

说明：首先对比7次关键字，新建了一棵败者树，并找到了最小元素来自归并段3的1这个元素，接下来继续进行比较，对比3次即可找到下一个最小的元素，如此下去，从而使整个有序。

3. 小结

说明：按照这里介绍的方法生成的初始归并段，若共N个记录，内存工作取可以容纳L个记录，则初始归并段数量r=N/L向上取整。可用“置换——选择排序”进一步减少初始归并段数量。