数据结构——外部排序

一、外部排序

1.1 基本思想

有时，待排序的文件很大，计算机内存不能容纳整个文件，这时候对文件就不能单纯的使用内部排序了，还得采取一些其他的策略。因此需要将待排序的记录存储到外存上，排序时再将数据一部分一部分地调用内存进行排序，在排序过程中需要多次进行内存和外存之间地交换，这种排序方法就成为外部排序。

文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读/写的机械动作所需的时间远远超过内存运算的时间，因此外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。

外部排序常采用的排序方法是归并排序，这种归并方法由两个不同的阶段组成：

根据内存缓冲区大小，将外存中的文件分成若干个长度为的子文件，依次读入内存并利用内部排序方法对它们排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并串或顺串；
对这些归并段进行逐趟归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止。

1.2 图解

（1）初始状态

（2）将数据结构——外部排序和分别存入输入缓冲区和输入缓冲区

（3）将输入缓冲区数据结构——外部排序和输入缓冲区的数据进行递增排序

(6) 对剩余数据结构——外部排序块内存依次进行上述操作，总共需要进行次读操作和次写操作，得到初始归并段。

（7）第一次归并：读入归并段数据结构——外部排序和归并段中的第一块磁盘（相对最小），进行排序:

（8）依次找出这两个输入缓冲区中最小元素，并将其移动到输出缓冲区中，当输出缓冲区满，则写入外存数据结构——外部排序

（9）继续找出这剩余元素中的最小元素，直到某一个缓冲区中空，则读入其所属归并段的后一个内存块的数据，并继续进行上述操作。直到两个缓冲区都空，且归并段数据结构——外部排序和归并段中的元素全部读入内存，此时归并段和归并段就得到了一个有序的递增序列。

当输入缓冲区空了时：

输入归并段数据结构——外部排序的第二块内存

1.3 外部排序的开销

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

1.4 优化：多路平衡归并

若改用数据结构——外部排序路归并排序，则只需趟归并，外部排序时的总读/写次数便减至。因此，增大归并路数，可减少归并趟数，进而减少总的磁盘次数。

一般地，对数据结构——外部排序个初始归并段，做路平衡归并,归并树可用严格叉树（即只有度为与度为的结点的叉树)来表示。第一趟可将个初始归并段归并为个归并段，以后每趟归并将个归并段归并成个归并段，直至最后形成一个大的归并段为止。数据结构——外部排序。可见，只要增大归并路数，或减少初始归并段个数，都能减少归并趟数，进而减少读写磁盘的次数，达到提高外部排序速度的目的。

二、败者树

为了使内部归并不受数据结构——外部排序的增大的影响，引入了败者树。败者树是属性选择排序的一种变体，可视为一棵完全二叉树。

将每个归并段的第一个元素作为叶子结点加入败者树中
从左至右、从上往下的更新分支节点的信息：判断其左右子树的大小，除了根节点（最上面那个结点）记录冠军来自哪个归并段外，其余各分支节点记录的是失败者来自哪个归并段。
取出最小的元素后，从其所属的归并段中取出下一个元素，依次与从叶子结点到根节点的各个结点所记录的败者信息进行对比。