数据结构--外部排序

一、外部排序
之前介绍的所有排序算法都是内部排序的算法，也就是说需要将所有数据装入内存再进行排序。但实际上会出现需要排序的数据太多无法全部装入内存的情况，这种情况下排序就是外部排序，外部排序的基本思想就是归并排序。
Tips：
归并排序：两个已排好序的数组，比较它们的第一个元素，选择小(或大)的放入目标数组，然后再比较各自的第一个元素，一直重复至一个数组为空，然后将另一个数组剩余元素一一放入目标数组。

1、排序思路
外部排序的基础思想也是归并。
假设所有数据都在一个文件中，这个文件大小恰好是可用内存的两倍，先从文件中读取一半的数据，然后用内部排序算法将其排序，接着将这一半数据存入一个新的文件。然后再从文件中读取剩下的一半的数据，同样在内存中将其排好序，存入一个新的文件中。最后，打开这两个文件，读取各自的第一个数据，比较后存入一个新文件，再读取、比较、存入……最后数据全部存入这个文件中，完成排序。
在第一次读取源数据的时候(即还没开始第一次归并)，每次读取都是读取主存能读取的最大数据量，假设为M，然后形成的单个“有序新文件”记为大小为M的“归并段(顺串)”
2、排序方法及时间
A、2-路平衡归并
举例：一个文件含有10000条记录，通过10次内部排序得到10个初始归并段R₁...R₁₀，其中每一段都含有1000个记录。然后两两归并：

image.png
由10个初始归并段得到一个有序文件，共进行了4趟归并，每一趟都从m个归并段得到ceil(m/2)个归并段，这种归并方法称为2-路平衡归并。
B、排序时间
外部排序所需总时间 = 内部排序所需时间(m * t_IS) + 外存信息读写时间(d * t_IO) + 内部归并所需时间(s * ut_mg)
其中：
M：经过内部排序之后得到的初始归并段个数
t_IS：得到一个初始归并段进行内部排序所需时间的平均值
d：总的读/写文件的次数
t_IO：进行一次外存读/写时间的平均值
s：归并的趟数
ut_mg：对u个记录进行内部归并所需时间
上例中：假设每个物理块(外存上信息的读/写以“物理块”为单位进行的)可以容纳200条记录，则每趟归并(一个归并段存储1000条记录)需进行50次“读”和50次“写”，4趟归并假设内部排序时所需进行的读/写使得在外排中共需进行500次读/写。
则所需外排时间为：10t_IS + 500t_IO + 4 * 10000ut_mg
由此可见，提高外排的效率应主要减少外存信息读写的次数d。
C、多路平衡归并
若对上例进行5路平衡归并：
image.png
则仅需两趟归并，总的读/写次数减少为2 * 100 + 100 = 300，比2路归并减少了200次的读/写。

二、胜者树和败者树
外部排序最耗时间的是磁盘读写，使用K路合并可以减少读写磁盘的次数，但会增加算法复杂度，使用败者树可以加快合并排序。
胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。
不同的是，胜者树的中间结点记录的是胜者的标号；而败者树的中间结点记录的败者的标号。
胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到。
1、胜者树
胜者树的一个优点是，如果一个选手的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果。

image.png

上图是胜者树的示例：
b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
b3 PK b0，b3胜b0负，内部结点ls[2]的值为3；
b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
b3 PK b1，b3胜b1负，内部结点ls[1]的值为3。
当叶子结点b3的值变为11时，重构的胜者树如下图所示。
b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
b3 PK b0，b0胜b3负，内部结点ls[2]的值为0；
b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
b0 PK b1，b1胜b0负，内部结点ls[1]的值为1。

image.png
2、败者树
败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。
image.png
上图是一棵败者树，规定数大者败。
b3 PK b4，b3胜b4负，内部结点ls[4]的值为4；
b3 PK b0，b3胜b0负，内部结点ls[2]的值为0；
b1 PK b2，b1胜b2负，内部结点ls[3]的值为2；
b3 PK b1，b3胜b1负，内部结点ls[1]的值为1；

在根结点ls[1]上又加了一个结点ls[0]=3，记录的最后的胜者。
败者树重构过程如下：
将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与上一级的父结点比较。
比赛沿着到根结点的路径不断进行，直到ls[1]处。把败者存放在结点ls[1]中，胜者存放在ls[0]中。

image.png
上图为当b3变为13时，败者树的重构图
败者树的重构跟胜者树是不一样的，败者树的重构只需要与其父结点比较。对照败者树原图来看，b3与结点ls[4]的原值比较，ls[4]中存放的原值是结点4，即b3与b4比较，b3负b4胜，则修改ls[4]的值为结点3。同理，以此类推，沿着根结点不断比赛，直至结束。
由上可知，败者树简化了重构。败者树的重构只是与该结点的父结点的记录有关，而胜者树的重构还与该结点的兄弟结点有关。