如：FC文件(20个元素): 5 15 35 30 20 45 35 5 65 75 40 50 60 70 30 40 25 10 45 55

　　步骤1:FC文件分割为各含10个单元素的两个临时文件FA,FB中。

　　FA: {5 35},{20 35}, {65 40 },{60 30 }, {25 45}

　　FB: {15 30} , {45 5} , {75 50} , {70 40}, {10 55}

　　步骤2：FA与FB归并排序成2元素的有序子表

　　FC: {5 15} {30 35}，{20 45} {5 35}，{65 75} {40 50}，{60 70} {30 40}，{10 25} {45 55}

　　步骤3: 继续将FC拆分为FA,FB，再次归并为FC中的4元素子表

　　FA: {5 15},{20 45},{65 75},{60 70},{10 25}

　　FB: {30 35},{5 35},{40 50},{30 40},{45 55}

　　FC: {5 15 30 35},{5 20 35 45},{40 50 65 67},{30 40 60 70},{10 25 45 55}

　　...继续归并(8元素->16元素->20元素)...

　　步骤6: 归并为FC中20个元素即得到完整的有序文件。

　　



　　修改直接归并排序，从较长子表开始，更高效的完成排序。算法根据文件FC和一个内存缓冲区建立有序子表。我们将原始文件中的数据以块形式读入到缓冲区中，然后用一种快速内部排序法(QuickSort)将块排好序。这些块被交替复制到文件fA和fB中。归并从具有较大初始长度的子表开始。

　　template

　　void MergeSort(BinFile& fc,int blockSize)

　　{ BinFile fA("fileA"，INOUT);

　　BinFile fB("fileB"，INOUT);

　　int size= int(fC.Size()),n=blockSize; //文件大小及块大小

　　int k=1,useA=1,readCount;

　　T * A;

　　fC.Reset(); //重置fc指针指向文件头

　　if(size <= blockSize) //对于fc小文件，从fc读入数据，排序后写回fc中

　　{ A=new T[size]; //申请存放数据的缓冲区并读入一块数据

　　if(A==NULL) //内存分配出错

　　{ cerr<<"MergeSort:memory allocation failure."<

　　exit(1);

　　}

　　fC.Read(A,size); //将fC的数据读入A中

　　QuickSort(A,0,(int)size-1); //对A进行快速排序

　　fC.Clear(); //清空文件fc并将排序后的数据写回文件fc中

　　fC.Write(A,size);

　　delete [] A; //释放缓冲区并返回

　　return;

　　}

　　else //如果文件大小超过了块大小

　　{ A = new T[blockSize];

　　if(A==NULL) //内存分配出错

　　{ cerr<<"MergeSort:memory allocation failure."<

　　exit(1);

　　}

　　while(!fC.EndFile())

　　{ readCount=fC.Read(A,blockSize); //读取blockSize大小的数据块文件

　　if(readCount==0) //如果没有读到数据返回

　　break;

　　//对数据块排序并交替写入到文件文件fA和fB中

　　QuickSort(A,0，readCount-1);

　　if(useA) //如果用到FA

　　{ fA.Write(A,readCount);

　　}else

　　{ fB.Write(A,readCount);

　　}

　　useA = !useA;

　　}

　　delete [] A; //数据写完释放A内存空间

　　}

　　Merge(fA,fB,fC,blockSize);// 将两个文件fA和fB中块大小为blockSize的归并段写回到fC中

　　k*=2; //将当前归并段大小加倍

　　n=k*blockSize;

　　while(n>文件大小时，fC仅剩下一个已排好序的归并段

　　{ Split(fA,fB,fC,k,blockSize); //循环分离归并段

　　Merge(fA,fB,fC,n);//排序后再重新写回fc

　　k*=2; //归并段循环加倍

　　n=k*blockSize; //加倍后的块大小

　　}

　　//删除临时文件

　　fA.Delete();

　　fB.Delete();

　　}
编辑tt娱乐城:http://www.