数据结构之外部排序

  外部排序就是对大型文件的排序，待排序的记录存放在外存。在排序的过程中，内存只存储文件的一部分记录，整个排序过程需要进行多次内外存间的数据交换。
  常用的外部排序方法是归并排序，一般分为两个阶段：在第一阶段，把文件中的记录分段读入内存，利用某种内部排序方法对记录段进行排序并输出到外存的另一个文件中，在新文件中形成许多有序的记录段，称为归并段；在第二阶段，对第一阶段形成的归并段用某种归并方法进行一趟趟地归并，使文件的有序段逐渐加长，直到将整个文件归并为一个有序段时为止。下面简单介绍常用的多路平衡归并方法。
  k 路平衡归并是指文件经外部排序的第一个阶段后，已经形成了由若千个初始归并段构成的文件。在这个基础上，反复将每次确定的k个归并段归并为一个有序段，将一个文件上的记录归并到另一个文件上。重复这个过程，直到文件中的所有记录都归并为一个有序段。
  设已经得到8个初始归并段，如下图所示，其中，b_i表示第i个归并段。

  在树形选择排序中，首先对n个记录的关键字进行两两比较，然后在[$\frac{n}{2}$]个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止，该过程可用一棵有n个叶子结点的完全二叉树表示，如下图(a)所示。其中，每个非终端结点中的关键字等于其左、右孩子结点中较小的关键字，则树根结点中的关键字即为所有叶子中的最小关键字。在输出最小关键字之后，更新最小关键字所在的叶子结点数据，然后从该叶子结点出发，与其左 (兄弟) 结点的关键字进行比较，修改从叶子结点到根的路径上各结点的关键字，则根结点的关键字即为次小关键字，如下图 (b)所示。重复该过程，即可完成对所有记录的排序。

  在上图所示的树中，每个非终端结点记录了其左、右孩子中的“优胜者”，所以称其为“胜者树”。反之，若在双亲结点中记录比较后的失败者，而让胜者去参加更上一层的比较，便可得到一棵“败者树”。这样一来，当优胜者到达父结点时，立刻就知道原先在此比较的失败者并与失败者进行比较，再次记录新的失败者并让优胜者去进行更上一层的比较。在败者树中，每个结点只需和其父结点进行比较，而在胜者树中，向上调整时结点需和兄弟结点比较，那么就需得到兄弟结点的位置信息，因此败者树更易于编程。
  下图所示的是一棵实现8路归并的败者树。

  为了简便起见，设每个记录为一个整数，败者树用数组 ls[] 表示，Is[i] 的值为败者所在归并段的段号，令ls[1] 是树根结点，ls[0] 是 ls1的父结点，Is[0]中存储每次选出的优胜者所在归并段的段号，输出时则取 ls[0]指示的归并段的当前记录。例如，在上图所示的败者树中，叶子结点的数据来自各个归并段；败者树的根结点 ls[1]的父结点 ls[0] 中存储了优胜者(最小记录)所在的归并段。下图所示的是输出一个记录后，重新调整后的败者树。

  【算法】利用败者树实现K路平衡归并。

#define K8
#define MINKEY-1		/*比所有关键字都小的一个值*/
#define MAXKEY 10000 	/*比所有关键字都大的一个值*/
int b[K+1];
void K merge(int ls[K])
/*ls[0]~ls[K-1]是败者树的内部结点。b[0]~b[K-1]分别存储K个初始归并段的当前记录*/
/*函数 Get_nextRec(i)从第i个归并段读取并返回当前记录，若归并段已空，返回MAXKEY*/
{
   
	int i,q;
	for(i= 0; i<K; i++)
		b[i] = Get_nextRec(i);	/*分别读取K个归并段的第一个关键字*/
	b[K]= MINKEY;
	for(i= 0; i<K; ++i) ls[i]=K;	/*创建败者树，设置ls中败者的初值*/
	for(i=K-1; i>=0; --i)			/*依次从b[K-1]、b[K-2]、...、b[0]出发调整败者树*/
		Adjust(ls, i);
	while (b[ls[0]]!=MAXKEY){
   		/*ls[0]记录本趟最小关键字所在的段号*/
		q = ls[0];					/*q 是当前最小关键字所在的归并段*/
		printf("%d", b[q]);			/*输出最小关键字*/
		b[g]= Get_nextRec(g);
		Adjust(ls, q);				/*调整败者树，选择新的最小关键字*/
	}/*while*/
}/*Kmerge*/		

  【函数】败者树的调整：从叶子结点到根结点进行调整。

void Adjust(int ls(K], int s)		/*败者树存储在 ls[1]~s[K-1]中，s 为记录所在的归并段号*/
{
   
	int t, temp;
	t=(s+K)/2;						/* t为 b[s]的父结点在败者树中的下标，K 是归并段数*/
	while(t>0) {
   					/*若没有到达树根，则继续*/
		if(b[s]> b[ls[t]]) {
   		/*与父结点指示的数据进行比较*/
			temp = s; s = ls[t];	/*s指示胜者，胜者将去参加更上一层的比较*/
			ls[t] = temp;			/*ls[t]记录败者所在的段号*/
		}/*if*/
		t= t/2;						/*向树根回退一层*/
	}/*while*/
	1s[0] = s;						/*1s[0]记录本趟最小关键字所在的段号*/
}/*Adjust*/