1.外部排序

外部排序是指数据量很大，一下子不能将所有的数据放入内存里面进行排序，只能一部分一部分从硬盘中读取数据，送入内部排序，将内部排序的结果取出，换下一批数据进行排序。

对于外部排序的提高的核心问题是：减少外部存储读写的次数。在一般情况下，对m个初始归并段进行K-路平衡归并，归并的趟数：s=以k为底，m的对数结果的向上取整值。

2.多路平衡归并的实现

由于K的增加能够减少m便能减少存储读写的次数，但是k的增加，内部归并时间也会增大，这样不是我们所希望的。所以我们在内部排序的时候如果能选择一种算法将不随K的选择而增加内部排序的时间的话，那就是比较好的，这就是”败者树“，看一下败者树的定义：在对一个序列进行初始堆的建立，然后每次让子孩子的大的去上一次，这样的过程就是构建一个败者树。

败者树的核心代码：

void Adjust(int s){	int t=(s+k)/2;	int temp;	while(t>0)	{		if(External[s] > External[LoserTree[t]])		{			temp = s;			s = LoserTree[t];			LoserTree[t]=temp;		}		t=t/2;	}	LoserTree[0]=s;}void CreateLoserTree(){	External[k]=MINKEY;	int i;	for(i=0;i
    
     =0;i--)Adjust(i);}void K_Merge(){	int i,p;	for(i=0;i
     
      =A[p].num)External[p]=MAXKEY;		else 		{			External[p]=A[p].arr[A[p].pos];			A[p].pos++;		}		Adjust(p);	}	cout<

3.置换—选择排序

在整个排序的过程中，选择最小的关键字和输入、输出交叉或平行进行。

过程：

假设初始待排序文件为FI，初始归并段文件为输出文件FO，内存工作区为WA，FO与WA的初始状态为空，并假设内存工作去WA的容量可容纳w个记录，则置换-选择排序的操作的过程为：

（1）、从FI输入w个记录到工作区WA。

（2）、从WA中选出其中关键字最小的记录，记为MINIMAX记录。

（3）、将MINIMAX记录输出到FO中去。

（4）、若FI不为空，则从FI输入下一个记录到WA中。

（5）、从WA中所有关键字比MINIMAX记录关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。

（6）、重复（3）～（5），直至WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标记到FO中去。

（7）、重复（2）～（6），直至WA为空。由此得到全部归并段。

当然由于置换选择排序出来的结果可能使得每个段不一样，这样用K路平衡归并树似乎不是很好，所以选择可以选择用哈夫曼树，这样构造的树称为最佳归并树。

转载地址：http://fgnfi.baihongyu.com/

你可能感兴趣的文章