C语言版的磁盘文件分片归并排序函数

这是一个很老的的C函数，用来实现大的磁盘文件排序。在以前DOS操作系统下，对磁盘文件的排序一般有3种方法：1、将磁盘文件装入内存排序，将排序结果保存到新的文件，这适用于很小的（64K以内）、不需要经常索引的文件；2、对磁盘文件按关键字进行分块排序后，形成一个索引文件。块的大小一般为512K，常采用B+树或者B-数算法，这种方法适用于需要经常索引的磁盘文件，如DBF文件；3、把磁盘文件分片排序后，形成很多排序片文件，然后将这些排序片文件合并起来，输出为一个排序文件，这种方法适用于很大的、但又不需要经常索引的磁盘文件。

可见，在DOS有限的内存条件下，磁盘文件分片归并排序是使用比较广泛的一种外存储器排序算法。现在计算机的物理内存一般足够大（最小的也有256MB吧），Windows的虚拟内存更是多达4个GB（对每一个应用程序而言），这对于很多磁盘文件的内存排序应该是足够了，况且现在的记录文件都放在各种数据库中，所以磁盘文件分片归并排序算法可能没有市场了（不过内存多路归并排序还是有市场的）。作为怀旧，把代码贴在这里，以免“失传”！

/**************************************************************************
*文件名:MERGE.H*
*编制人:湖北省公安县统计局毛泽发*
*日期:1991.8*
**************************************************************************/

#defineS_IREAD0x0100
#defineS_IWRITE0x0080

#ifdefined(__TINY__)||defined(__SMALL__)||defined(__MENIUM__)
#defineSSIZE25600/*排序缓冲区字节*/
#defineNULL0
#else
#defineSSIZE65024/*排序缓冲区字节*/
#defineNULL0L
#endif
#defineMAXMERGE4/*排序合并每趟每次最大片*/
#defineMAXMEREC(SSIZE/(MAXMERGE+1))/*文件最大记录长*/

typedefintcdeclmercmpf(constvoid*,constvoid*);

/*通用排序函数.
参数:排序文件名;原文件名;原文件头字节数;文件记录长;用户提供的比较函数.
返回值:成功>0;内存不够.记录超长返回0;文件操作出错-1*/
intfmerge(char*foname,char*finame,intftops,intlrd,mercmpf*cmpf);

/**************************************************************************
*文件名:MERGE.C*
*编制人:湖北省公安县统计局毛泽发*
*日期:1991.8*
**************************************************************************/

#include<io.h>
#include<string.h>
#include<fcntl.h>
#include<stdio.h>
#include<stdlib.h>
#include"merge.h"

staticmercmpf*mercmp = NULL;/*比较函数*/

staticchar*merbuf=NULL;/*排序动态缓冲区*/
staticchar*filetop=NULL;/*原文件文件头存放动态缓冲区*/
staticintfiletopchs;/*原文件文件头长*/
staticintmerlrd;/*文件记录长*/

staticintoutfile(char*fname,unsignedsize,intflag);
staticintformerge(char*foname,char*finame,char*tmp,unsignedm);
staticdomerge(char*foname,char*tmp1,char*tmp2,intirun);
staticvoidsmerge(int*md,intm,char*buf[],intoutf,char*outbuf,intsize);
staticintdopass(char*name1,char*name2,intirun);

/*通用排序函数.
参数:排序文件名;原文件名;原文件头字节数;文件记录长;用户提供的比较函数.
返回值:成功>0;内存不够.记录超长返回0;文件操作出错-1*/
intfmerge(char*foname,char*finame,intftops,intlrd,mercmpf*cmpf)
{
chartmp1[68],tmp2[68];
intirun;
unsignedsize;
if(lrd>MAXMEREC)return0;/*记录超长*/
merlrd=lrd;
size=(SSIZE/lrd)*lrd;/*排序缓冲区实际长*/
if((merbuf=(char*)malloc(size))==NULL)return0;/*分配动态缓冲区*/
if(ftops&&(filetop=(char*)malloc(ftops))==NULL)return0;
filetopchs=ftops;
mercmp=cmpf;
strcpy(tmp1,"&&&1");/*临时文件名*/
strcpy(tmp2,"&&&2");
irun=formerge(foname,finame,tmp1,size);/*分片排序*/
if(irun>1)/*如果排序片大于1*/
irun=domerge(foname,tmp1,tmp2,irun);/*合并排序片*/
free(merbuf);
if(filetopchs)free(filetop);
returnirun;
}
/*写一排序片文件*/
staticintoutfile(char*fname,unsignedsize,intflag)
{
inth,c;
if((h=open(fname,O_WRONLY|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE))==-1)
return-1;
if(flag&&filetopchs)/*如果是最终文件同时原文件有文件头*/
write(h,filetop,filetopchs);/*写入文件头内容*/
c=write(h,merbuf,size);/*写排序片到文件*/
close(h);
returnc;
}
/*分片排序*/
staticintformerge(char*foname,char*finame,char*tmp,unsignedm)
{
unsignedirun,ret;
intf,flag=0;
chartmpname[68];
if((f=open(finame,O_RDONLY|O_BINARY))==-1)return-1;/*打开原文件*/
if(filetopchs)/*如有文件头,保存其内容到缓冲区*/
read(f,filetop,filetopchs);
irun=0;
do{
ret=read(f,merbuf,m);/*读一排序片到排序缓冲区*/
if(ret==0||ret==0xffff)break;/*原文件结束或出错,退出*/
qsort(merbuf,ret/merlrd,merlrd,mercmp);/*排序*/
if(ret==m||irun>0)/*如原文件长大于或等于一排序片长*/
sprintf(tmpname,"%s.%03d",tmp,irun);/*采用临时文件名*/
else{/*否则,直接用排序文件名*/
strcpy(tmpname,foname);
flag=1;/*最终文件标记*/
}
ret=outfile(tmpname,ret,flag);/*写排序片*/
irun++;
}while(ret==m);
close(f);
if(ret==0xffff)returnret;/*出错返回-1*/
returnirun;/*返回排序片数*/
}
/*分配每一合并趟不同临时文件名;控制合并趟数*/
staticdomerge(char*foname,char*tmp1,char*tmp2,intirun)
{
char*p;
while(irun>1){
if(irun<=MAXMERGE)strcpy(tmp2,foname);
irun=dopass(tmp1,tmp2,irun);
p=tmp1;
tmp1=tmp2;
tmp2=p;
}
returnirun;
}
/*执行合并趟,计算.分配每次合并所需文件数,缓冲区大小,控制每次合并的执行*/
staticintdopass(char*name1,char*name2,intirun)
{
intfi,i,nrun,m,size;
charoname[68],inname[68],*p[MAXMERGE],*q;
intmd[MAXMERGE],fo;
size=SSIZE/merlrd;/*合并缓冲区容纳记录数*/
nrun=0;
for(fi=0;fi<irun;fi+=MAXMERGE){
m=irun-fi;/*每次合并实际排序片数*/
if(m>MAXMERGE)m=MAXMERGE;
for(i=0;i<m;i++)p[i]=merbuf+(i*merlrd);/*分配读缓冲区*/
if(irun<=MAXMERGE)strcpy(oname,name2);/*最终合并形成排序文件*/
elsesprintf(oname,"%s.%03d",name2,nrun);/*中间合并采用临时文件*/
if((fo=open(oname,O_WRONLY|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE))==-1)
break;/*打开写文件*/
i=0;
do{/*分别打开读文件*/
sprintf(inname,"%s.%03d",name1,fi+i);
md[i]=open(inname,O_RDONLY|O_BINARY);
}while(md[i++]!=-1&&i<m);
if(i!=m){
close(fo);
for(fi=0;fi<i;fi++)close(md[fi]);
break;
}
if(irun<=MAXMERGE&&filetopchs)/*最终合并写文件头(如有)*/
write(fo,filetop,filetopchs);
q=merbuf+(m*merlrd);/*分配写缓冲区*/
smerge(md,m,p,fo,q,size-m);/*合并*/
for(i=0;i<m;i++){/*删除各排序片文件*/
close(md[i]);
sprintf(inname,"%s.%03d",name1,fi+i);
unlink(inname);
}
close(fo);
nrun++;
}
if(nrun!=(irun+MAXMERGE-1)/MAXMERGE)return-1;
returnnrun;
}
/*执行实际排序片合并*/
staticvoidsmerge(int*md,intm,char*buf[],intoutf,char*outbuf,intsize)
{
inti,j,n=merlrd,w=merlrd*size;
char*s=buf[0],*p,*q=outbuf,*end=q+w;
for(i=0;i<m;i++)/*从各片文件中读第一条记录*/
read(md[i],buf[i],n);
while(1){
if(n==merlrd){/*如各片文件均有记录,各片记录反向插入排序*/
for(i=1;i<m;i++){
for(p=buf[i],j=i-1;j>=0&&mercmp(p,buf[j])>0;j--)
buf[j+1]=buf[j];
buf[j+1]=p;
}
}
elsem--;/*一片文件内容结束*/
if(!m){/*如所有片文件结束,写缓冲区残余记录,退出*/
if(q!=outbuf)write(outf,outbuf,q-outbuf);
break;
}
if(q==end){/*刷新一次写缓冲区到文件*/
if(write(outf,outbuf,end-outbuf)!=w)break;
q=outbuf;
}
i=m-1;
j=(buf[i]-s)/merlrd;
memmove(q,buf[i],merlrd);/*将各片记录中值最小(大)者移入写缓冲区*/
q+=merlrd;
n=read(md[j],buf[i],merlrd);/*从该片中读下一记录,继续*/
}
}

可以看到，上面2个文件时间是1991年的，真是老古董了，如MERGE.H文件开头就没有什么诸如#ifndef __MERGE_H......的代码，我记得那个时候好像没这个写法的。函数里面当初也作了很详细的注释，所以算法就不再讲了（要讲我还得先分析代码，早忘记了 ^_^ ）。

为了示范该函数的使用方法，我还是用BCB6写了一个简单的演示程序，如果你想试一下老古董，不妨也写一个？可以将MERGE.H文件中的排序缓冲区加大一些，可提高排序速度。

//---------------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
#include"merge.h"

#pragmahdrstop

#defineTOPSTRING"湖北省公安县统计局毛泽发"
#defineTOP_SIZE30
#defineRECORD_SIZE53
#defineRECORD_COUNT10000

//---------------------------------------------------------------------------
/*为了方便观察，随机生成了一个RECORD_COUNT行的文本文件*/
voidMakeFile(char*filename)
{
inti,j;
longv[4];
FILE*f;
f=fopen(filename,"w");
fprintf(f,"%s ",TOPSTRING);
randomize();
for(i=0;i<RECORD_COUNT;i++)
{
for(j=0;j<4;j++)
v[j]=random(0x7fffffff);
fprintf(f,"%12ld%12ld%12ld%12ld ",v[0],v[1],v[2],v[3]);
}
fclose(f);
}


intcdeclCompRecord(constvoid*ra,constvoid*rb)
{
inta[4],b[4];
inti,n;
sscanf((char*)ra,"%ld%ld%ld%ld",&a[0],&a[1],&a[2],&a[3]);
sscanf((char*)rb,"%ld%ld%ld%ld",&b[0],&b[1],&b[2],&b[3]);
for(n=0,i=0;i<4&&n==0;i++)
n=a[i]-b[i];
returnn;
}

#pragmaargsused
intmain(intargc,char*argv[])
{
printf("正在随机制造一个文本文件d:\test.txt... ");
MakeFile("d:\test.txt");
printf("正在进行磁盘文件排序，排序文件d:\sort.text... ");
fmerge("d:\sort.txt","d:\test.txt",TOP_SIZE,RECORD_SIZE,CompRecord);
printf("磁盘文件排序完毕! ");
system("pause");
return0;
}
//---------------------------------------------------------------------------

如有错误，或者你有什么好的建议请来信：[e-mail]

发现代码贴上去总是走样，文件路径‘\\’也成了‘\’，‘\n’也没了，MakeFile的2句写记录语句应该分别是，不然，测试会出问题：

fprintf(f, "%s\n", TOPSTRING);

和

fprintf(f, "%12ld %12ld %12ld %12ld\n", v[0], v[1], v[2], v[3]);