外排序.cpp

先用内排序对随即产生的内n个3位数的整数排好序

/*
	        用败者树进行外排序
			author:FangYuhao
			date:2008/10/25
            describtion:
			先用内排序对随即产生的内n个3位数的整数排好序，存放在一个文件中，
			共产生m个有序文件，然后对这m个文件利用败者树进行多路平衡归并，
			得到一个有n*m个三位数的有序文件。
 */
#include	<iostream>
#include	<algorithm>
#include    <ctime>
using		namespace    std;
#define		N 121
#define		M 5
FILE		*fp[M+1];
char		*name[6] = {"f0.dat","f1.dat","f2.dat","f3.dat","f4.dat","f5.dat"};
int         ls[M] , b[M + 1] ;
void		creatfile()
{
			int   a[N] , i , j ,seed , temp , n;
			srand(time(NULL));
			for(j = 0 ; j < M  ; j++)
			{
			       for(i = 1 ; i < N ; i++) a[i] = rand()%1000;
				   sort(a+1 ,  a+N);
				   fp[j] = fopen(name[j],"wb");
				   temp = 10000;
				   for(i = 1 ; i < N ; i++)
					    fwrite(&a[i],sizeof(int),1,fp[j]);
				   fwrite(&temp,sizeof(int),1,fp[j]); //写入结束标志，这里用10000表示
				   fclose(fp[j]);
			}
}
void		adjust(int ls[] , int b[] , int s ,int k) // 败者树调整函数
{
			int t , temp;
			t = (s + k)  / 2;
			while(t)
			{
			        if (b[s] > b[ls[t]])
					{ 
						temp = s ;
						s = ls[t];
						ls[t] = temp;
					}
					t /= 2;
			}
			ls[0] = s;
}
void        crttree(int ls[] , int b[] , int k) // 建立败者树
{
            int  i ;
			b[k] = -100;
			for(i = 0 ; i <= k ; i++) ls[i] = k;
			for(i = k-1 ; i >= 0 ; i--)
				   adjust(ls,b,i,k);

}
void		kpathmerge(int ls[] , int b[] , int k) //k路平衡归并
{
			int i ,  q;
			for(i = 0 ; i < k ; i++) fp[i] = fopen(name[i],"rb");
			fp[k] = fopen(name[k],"wb");
			for(i = 0 ; i < k ; i++)
				 fread(&b[i],sizeof(int),1,fp[i]);
			crttree(ls,b,k);
			while(b[ls[0]] != 10000)
			{
			         q = ls[0];
					 fwrite(&b[q] ,  sizeof(int) , 1 , fp[k]);
					 fread(&b[q] , sizeof(int) , 1 , fp[q]);
					 adjust(ls,b,q,k);
			}
			for(i = 0 ; i <= k ; i++) fclose(fp[i]);
}
int			main()
{
            int  n , temp , ans;
			creatfile();
			kpathmerge(ls,b,M);
			n = 0;
			fp[5] = fopen(name[5],"rb");
			while(!feof(fp[5]))        //输出结果到屏幕
			{
			        fread(&temp , sizeof(int) , 1 , fp[5]);
					printf("%6d",temp);
					n++;
					if(n %10 == 0) printf("\n");
			}
			fclose(fp[5]);
			return 0;
}