外部排序
有时，待排序的文件很大，计算机内存不能容纳整个文件，这时候对文件就不能使用内部排序了（这里做一下说明，其实所有的排序都是在内存中做的，这里说的内部排序是指待排序的内容在内存中就可以完成，而外部排序是指待排序的内容不能在内存中一下子完成，它需要做内外存的内容交换），外部排序常采用的排序方法也是归并排序，
这种归并方法由两个不同的阶段组成：
1、采用适当的内部排序方法对输入文件的每个片段进行排序，将排好序的片段（成为归并段）写到外部存储器中（通常由一个可用的磁盘作为临时缓冲区），这样临时缓冲区中的每个归并段的内容是有序的。
2、利用归并算法，归并第一阶段生成的归并段，直到只剩下一个归并段为止。
例如要对外存中4500个记录进行归并，而内存大小只能容纳750个记录，在第一阶段，我们可以每次读取750个记录进行排序，这样可以分六次读取，进行排序，可以得到六个有序的归并段，如下图：
每个归并段的大小是750个记录，记住，这些归并段已经全部写到临时缓冲区（由一个可用的磁盘充当）内了，这是第一步的排序结果。
完成第二步该怎么做呢？这时候归并算法就有用处了，算法描述如下：
1、将内存空间划分为三份，每份大小250个记录，其中两个用作输入缓冲区，另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并，先从每个归并段中读取250个记录到输入缓冲区，对其归并，归并结果放到输出缓冲区，当输出缓冲区满后，将其写道临时缓冲区内，如果某个输入缓冲区空了，则从相应的归并段中再读取250个记录进行继续归并，反复以上步骤，直至Segment_1和Segment_2全都排好序，形成一个大小为1500的记录，然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。
2、对归并好的大小为1500的记录进行如同步骤1一样的操作，进行继续排序，直至最后形成大小为4500的归并段，至此，排序结束。
以上对外部排序如何使用归并算法进行排序进行了简要总结，提高外部排序需要考虑以下问题：
1、如何减少排序所需的归并趟数。
2、如果高效利用程序缓冲区，使得输入、输出和CPU运行尽可能地重叠。
3、如何生成初始归并段（Segment）和如何对归并段进行归并。
举个例子
我们假设需要排序的int数有12个，内存一次只能装下3个int数。
接下来把12个数据分成4份，然后排序成有序子串：
然后把子串进行两两合并：
优化策略
因为硬盘的读写速度比内存要慢的多，按照以上这种方法，每个数据都从硬盘读了三次，写了三次，要花很多时间。
解释下：例如对于数据2，我们把无序的12个数据分成有序的4个子串需要读写各一次，把2份3个有序子串合并成6个有序子串读写各一次；把2份6个有序子串合并从12个有序子串读写各一次，一共需要读写各3次。
在进行有序子串合并的时候，不采取两两合并的方法，而是可以3个子串，或4个子串一起来合并。
多路归并排序
外部排序最常用的算法是归并排序，而多路归并排序的流程与思想也比较简单，在此不再赘言。
但值得注意的是其重要的子算法
- 置换-选择排序
n个记录分为m个规模较小的记录段，如果被划分的每个小记录段规模不够小，仍然无法完全读入内存，则无法用内排序得到初始归并段，因此需要一种适用于初始归并段规模的，高效的且不受内存空间限制的排序算法，即置换-选择排序。 - 最佳归并树
将当前的m组（每组含有k个有序记录段）记录归并为m个有序记录段的过程称为一趟归并，可见每个记录在每趟归并中需要两次I/O操作（读写操作各一次）。读写操作是非常耗时的，可见减少归并次数可以提高效率。为了使得归并次数最少，需用到最佳归并树。 - 败者树
归并排序算法中有一个多次出现的步骤是从当前k个值中用某种算法选出最值，可见提高选最值的效率也是整个归并排序算法效率提高的关键。这就需要用到败者树。
置换-选择排序
/**
*置换-选择排序的简单描述
*/
typedef struct{
RcdType rec; //记录
KeyType key; //从记录中抽取的关键字
int rnum; //所属归并段的段号
}RcdNode, WorkArea[w]; //内存工作区，容量为w
void Replace_Selection(LoserTree &ls,WorkArea &wa, FILE *fi, FILE *fo){
// 在败者树ls和内存工作区wa上用置换-选择排序求初始归并段,fi为输入文件
//（只读文件）指针,fo为输出文件(只写文件)指针，两个文件均已打开
Construct_Loser(ls,wa); //初建败者树
rc = rmax = 1; //rc指示当前生产的初始归并段的段号
//rmax指示wa中关键字所属初始归并段的最大段号
while(rc <= rmax){ //"rc = rmax+1" 标志输入文件的置换-选择排序已完成
get_run(ls,wa); //求得一个初始归并段
fwrite(&RUNEND_SYMBOL,sizeof(struct RcdType),1,fo); //将段结束标志输入输出文件
rc = wa[ls[0]].rnum; //设置下一段的段号
}
}
void get_run (LoserTree &ls,WorkArea &wa){
//求得一个初始归并段，fi为输入文件指针，fo为输出文件指针
while(wa[ls[0]].rnum == rc){ //选得的MINIMAX记录属当前段时
q = ls[0]; //q知识MINIMAX记录在wa中的位置
minimax = wa[q].key;
}
fwrite(&wa[q].rec,sizeof(RcdType),1,fo); //将刚选好的MINIMAX记录写入输出文件
if(feof(fi)) {wa[q].rnum = rmax +1; wa[q].key = MAXKEY;}
//输入文件结束，虚设记录(属"rmax+1"段)
//输入文件非空时
else{
fread(&wa[q].rec,sizeof(RcdType),1,fi); //从输入文件读入下一记录
wa[q].key = wa[q].rec.key; //提取关键字
if(wa[q].key <minimax){ //新读入的记录属下一段
rmax = rc +1;
wa[q].rnum = rmax;
}
else
wa[q].rnum = rc; //新读入的记录属当前段
}
Select_MiniMax(ls,wa,q); 选择新的MINIMAX记录
}
void Select_MiniMax(LoserTree &ls,WorkArea wa,int q){
//从wa[q]起到败者树的根比较选择MINIMAX记录，并由q指示它所在的归并段
for(t = (w+q)/2,p = ls[t];t>0; t= t/2,p = ls[t]){
if(wa[p].rnum <wa[q].rnum || wa[p].rnum == wa[q].rnum && wa[p].key <wa[q].key){
q <-->ls[t]; //q指示新的胜利者
}
}
ls[0] = q;
}
}
void Construct_Loser(LoserTree &ls,WorkArea &wa){
//输入w个记录到内存工作区wa,建得败者树ls,选出关键字最小的记录并由s指示
//其在wa中的位置
for(i = 0 ; i <w; ++i){
wa[i].rnum = wa[i].key = ls[i] = 0; //工作区初始化
}
for(i = w-1;i>=0; -- i){
fread(&wa[i].rec,sizeof(RcdType),1,fi); //输入一个记录
wa[i].key = wa[i].rec.key; // 提取关键字
wa[i].rnum = 1; //其段号为"1"
Select_MiniMax(ls,wa,i); //调整败者
}
}
最佳归并树
归并的过程可以用一棵树来形象地描述，这棵树称为归并树，
为了优化归并树的带权路径长度，可以运用哈弗曼树。败者树
为了突出如何利用败者树进行归并，在算法中避开了外存信息存取的细节，可以认为归并段已在内存。
typedef int LoserTree[k]; //败者树是完全二叉树且不含叶子，可采用顺序存储结构
typedef struct{
KeyType key;
}ExNode,External[k+1]; //外结点，只存放待归并记录的关键字
void K_Merge(LoserTree &ls,External &b){
/*利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段。
b[0]至b[k-1]为败者树上的k个叶子结点，分别存放k个输入归并段中当前记录的关键字。
*/
for(i = 0;i<k; ++ i) input(b[i].key); //分别从k个输入归并段读入该段当前第一个记录的关键字到外结点
CreateLoserTree(ls); //建败者树ls，选得最小关键字为b[ls[0]].key
while(b[ls[0]].key != MAXKEY){
q = ls[0]; //q指示当前最小关键字所在归并段
output(q); //将编号为q的归并段中当前（关键字为b[q].key）的记录写至输出归 并段
input(b[q].key,q);// 从编号为q的输入归并段中读取下一个记录的关键字
Adjust(ls,q); //调整败者树，选择性的最小关键字
}//while
output(ls[0]); //将含最大关键字MAXKEY的记录写至输出归并段
}
void CreateLoserTree(LoserTree &ls){
//已知b[0]到b[k-1]为完全二叉树ls的叶子结点存在k个关键字
//，沿从叶子到根的k条路径将ls调整为败者树
b[k].key = MINKEY; //设MINKEY为关键字可能的最小值
for(i = 0;i < k;++i){
ls[i] = k; //设置ls中"败者"的初值
}
for(i = k-1; i>=0; - - i) Adjust(ls,i);
//依次从b[k-1],b[k-2],……,b[0]出发调整败者
}
while Adjust(LoserTree &ls,int s){
//沿从叶子结点b[s]到根结点ls[0]的路径调整败者树
t = (s+k)/2;
while(t >0){
if(b[s].key > b[ls[t]].key) s<-->ls[t]; //s指示新的胜者
t=t/2;
}
ls[0] = s;
}
由序号构造结点的好处是,不仅可以找到记录值，还可以找到其所在的归并段，以便于下一个记录读入内存取代刚选出的最值。
为什么得用败者树，而不是用堆？：
时间空间复杂度分析
外部排序的时间复杂度涉及很多方面，且分析较为复杂，一般考试不会让考试分析整个流程中与
时间复杂度相关的每一个细节，因此只需要注意以下几点即可：
1 m个初始归并段进行k路归并，归并的趟数为[logkm]
2 每一次归并，所有记录都要进行两次I/O操作。
3 置换-选择排序这一步中，所有记录都要进行两次I/O操作
4 置换-选择排序中，选最值那一步的时间复杂度要根据考试要求的选择算法而定
5 k路归并的败者树的高度为[log2k]+1，因此利用败者树从k个记录中选出最值需要进行[log2k]此比较，即
时间复杂度O(log2k)
6 k路归并的败者树的建树时间复杂度为O(klog2k)
注意k路归并败者树，不是k叉败者树，而是一颗二叉树
空间复杂度
显然所有步骤中的空间复杂度都是常量，因此是O(1)
多路归并示例
为了方便讲解，我们假设内存一共可以装4个int型数据。
刚才我们是采取两两合并的方式，现在我们可以采取4个有序子串一起合并的方式，这样的话，每个数据从硬盘读写的次数各需要2次就可以了。如图：
4个有序子串的合并，叫4路归并。如果是n个有序子串的合并，就把它称为n路归并。n并非越大越好。
置换选择
n不是越大越好，那么我们可以想办法减少有序子串的总个数。这样，也能减少数据从硬盘读写的次数。
以前面的12个无序数据为例：
例如我们可以从12个数据读取3个存到内存中，然后从内存中选出最小的那个数放进子串p1里；之后再从剩余的9个数据读取一个放到内存中，然后再从内存中选出一个数放进子串p1里，这个数必须满足比p1中的其他数大，且在内存中尽量小。这样一直重复，直到内存中的数都比p1中的数小，这时p1子串存放结束，继续来p2子串的存放，例如（这时假设内存只能存放3个int型数据）：
读入3个到内存中，且选出一个最小的到子串p1：
这个时候已经没有符合要求的数了，且内存已满，进而用p2子串来存放，以此类推。
通过这种方法，p1子串存放了4个数据，而原来的那种方法p1子串只能存放3个数据。
这样子的话，最后只生成了2个有序子串，我们把这种方法称之为置换选择。按照这种方法，最好的情况下，所有数据只生成一个有序子串；最坏的情况下，和原来没采取置换选择算法一样，还是4个子串，那平均性能如何呢？
结论：如果内存可以容纳n个元素的话，那么平均每个子串的长度为2m，也就是说，使用置换选择算法我们可以减少一半的子串数。
这种方法适合要排序的数据太多，以至于内存一次性装载不下。只能通过把数据分几次的方式来排序，把这种方法称为外部排序。
京公网安备 11010502036488号