外排序完整版代码

 

   那篇外排摸索文章里的代码都是我一点一点修改的片段，现在有一个可以运行的完整版本。

   由于自己写的快排效率稍差，所以改用STL快排，然后写了一个简单的一次自动化归并所有文件的函数，但发现还不如一次合并来的快，不解中，但先贴出代码，继续持续更新。

    附件有一个生成随机数据的代码，10的7次方个不重复的整数。

 

 

//============================================================================
// Name        : Sort.cpp
// Author      : ZeaLoVe

//============================================================================

#include <algorithm>
#include "mem.h"
#include <iostream>
#include <fstream>
#include <string>
#include "time.h"
#include "math.h"
using namespace std;


const int bufSize = 1024;
const int W_BUF=4096;
const int K=16;

void dataInit()//生成数据
{
	int i;
	ofstream file(".//data.txt");
    if(!file.is_open())
    {
    	cout<<"NO File!"<<endl;
    }
    srand((int)time(0));
	for(i=0;i<100000000;++i)//生成的整数数量
	{
		file << rand()%100000000<<" ";//控制数据的范围
	}
	file.close();
}
void showTimeUsed(time_t start)
{
	time_t end=time(NULL);
	cout<<"Use:"<<(end-start)<<"s"<<endl;
}

char* getFileName(int num,int times)
{
     char* filename=(char*)malloc(sizeof(char)*50);
     sprintf(filename,".//data%d-%d.txt",num,times);
     return filename;
}

//从filename的文件中，读取totalSize个整形，并分割成每块含有numSize个整形的小文件
int dataCut(char* filename,int numSize,int totalSize)
{
	int i;
	int cutnum = ceil((double)totalSize/numSize);//计算切割成多少个文件
	int curNum=0;
	int numleft=totalSize%numSize;//计算最后一个文件的数字
	cout<<cutnum<<"  "<<numleft<<endl;

	ifstream input(filename);//输入流

	int* a=new int[numSize];
	while(1)
	{
   	    curNum++;
		ofstream output(getFileName(curNum,0));
		if(curNum>cutnum  )
   	    {
			if(numleft == 0) break;
 	  	    for(i=0;i<numleft;++i)
	  	    {
	            input>>a[i];
	        }
	        sort(a,a+numleft);

   	    	for(i=0;i<numleft;++i)
   	    	{
   	    		output<<a[i]<<" "<<flush;
   	    	}
   	    	output.close();
   	    	break;
   	    }
  	    for(i=0;i<numSize;++i)
  	    {
            input>>a[i];
        }
  	    sort(a,a+numSize);

   	    for(i=0;i<numSize;++i)
        {
   	        output<<a[i]<<" "<<flush;
        }
   	    output.close();
	}
    input.close();
    delete[] a;
    return cutnum;//返回文件数目
}

struct AutoBuf
{
#ifdef _DEBUG_
	string name;
#endif
	int cur;//当前数据的索引
	int* buf;//数据缓存
	int size;//缓存区现有数据大小
	bool isLast;//是否已经从文件读完
	ifstream in;
	AutoBuf()
	{
		cur=0;
		size=0;
		isLast=false;
//		buf=(int*)malloc(sizeof(int)*bufSize);
		buf=new int[bufSize];
	}
	~AutoBuf()
	{
		in.close();
//		cout<<name<<" has:"<<sum<<" ints"<<endl;
		delete[] buf;
	}
	void AttachFile(const char* filename)
	{
#ifdef _DEBUG_
	   name=filename;
#endif
		in.open(filename);
	}
	int read()//从指定文件中读取
	{
		if( !in.is_open() )
		{
#ifdef _DEBUG_
	cout<<name<<" file not open!"<<endl;
#endif
			return -1;
		}
		int i=0;
		while( i<bufSize && in>>buf[i++] )
		{
		}
		size=i;//buf中有多少个数据
#ifdef _DEBUG_
	   cout<<"read size:"<<size<<endl;
#endif
		cur=0;
		if( size < bufSize ) isLast=true;
		return size;
	}
	int autoGet()//还可以修改，已经修正-1的Bug
	{
		if(cur < size)
		{
//			sum++;
			return buf[cur++];
		}
		else
		{
			if( isLast )
			{
				//已经没数据了
				return -1;
			}
			else//还有，可以继续读
			{
				if( read()==-1 )//读取失败
				{
					return -1;
				}
				else
				{
					return autoGet();
				}
			}
		}
	}
};

struct AutoWriter
{
//	int sum=0;
	int *buf;
	int size;//缓存中的整形数
	ofstream out;
	AutoWriter()
	{
		size=0;
		buf=new int[W_BUF];
	}
	~AutoWriter()
	{
		Flush();
		out.close();
		delete[] buf;
//		cout<<"Total ints:"<<sum<<endl;
	}
	void AttachFile(const char * filename)
	{
		out.open(filename);
	}
	void put(int num)
	{
//		cout<<num<<" ";
		if( size < W_BUF )
		{
			buf[size++]=num;
		}
		else
		{
	         Flush();
	         buf[size++]=num;
		}
	}
	void Flush()
	{
		for(int i=0;i<W_BUF;++i)//输出文件
		{
			out<<buf[i]<<" ";
//			sum++;
		}
		size=0;
		out.flush();
	}
};
struct heapNode
{
	AutoBuf* data;//数据源
	int Knum;//当前读入数值
};

typedef heapNode* Point;

void adjust_heap(Point* a , int i)//调节该点 OK
{
	Point tmp=a[i];
	while( i > 1 )
	{
		if( a[i>>1]->Knum > tmp->Knum)
		{
			a[i]=a[i>>1];
			i>>=1;
		}
		else
		{
			break;
		}
	}
    a[i]=tmp;
}
void make_heap( Point* heap , int size )// OK
{
	int i;
	for(i=1;i<=size;i++)
	{
		adjust_heap(heap, i);
	}
}
void adjustDown_heap(Point* a ,int size)
{
	Point tmp = a[1];
	int i=1;
    while( i<= size )//有孩子
    {
    	if( 2*i > size ) break;//越界判断！！！！！
    	if( (2*i+1) > size)//只有一个孩子
    	{
    		if( tmp->Knum < a[2*i]->Knum )
    		{
    			break;
    		}
    		else
    		{
    			a[i]=a[2*i];
    			i=2*i;
    			continue;
    		}
    	}
    	if( tmp->Knum < a[2*i]->Knum && tmp->Knum < a[(2*i+1)]->Knum )//两个孩子
    	{
    		break;
    	}
    	else//选择和较小的孩子节点替换
    	{
    		if( a[2*i]->Knum < a[(2*i+1)]->Knum )
    		{
    			a[i]=a[2*i] ;
    			i*=2;
    		}
    		else
    		{
    			a[i]=a[(2*i+1)];
    			i=2*i+1;
    		}
    	}
    }
    a[i] = tmp;
}


void K_merge(const char* targetFile,int start=1,int end=K,int times=0)//K路归并成一路
{
#ifdef _DEBUG_
	  cout<<"Merge from "<<start<<" to "<<end<<endl;
#endif
    int i;
    int size = end-start+1;
    Point node[size+1];//这是一个指向heapNode对象的指针数组
    Point tmp;
    for(i=0;i<=size;++i)//必须分配heapNode 对象的空间
    	node[i]=new heapNode;

    AutoBuf buf[size+1];
    AutoWriter w;
    w.AttachFile(targetFile);

    for(i=1;i<=size;++i)
    {
          node[i]->data = buf+i;
          node[i]->data->AttachFile(getFileName(start+i-1,times));//将自动缓存和文件绑定
          node[i]->data->read();// 读取文件的其中一块
          node[i]->Knum=node[i]->data->autoGet();//获取第一个数字
    }

    make_heap(node,size);
    int Size=size;
    while( Size > 0 )
    {
    	 w.put(node[1]->Knum);

    	 node[1]->Knum=node[1]->data->autoGet();

    	 if( node[1]->Knum !=-1)
    	 {
    		 adjustDown_heap(node ,Size);
    	 }
    	 else//堆大小减1，同时将其塞入废弃区
    	 {
    		 tmp=node[1];
    		 node[1]=node[Size];
    		 node[Size]=tmp;
    		 --Size;
    		 adjustDown_heap(node ,Size);
    	 }
    }
    for(i=1;i<=size;++i) delete node[i];
//    out.close();
}

void  deleteFiles(int number)
{
	 for(int i=1;i<=number;++i)
	 {
		 remove(getFileName(i,0));
	 }
}

void All_merge(const char* finalFile,int fileCount)
{
	int i;
	int times=0;
	int leftNum;
	int curFileNum=fileCount;
	while( curFileNum/K != 0 )
	{
		leftNum=curFileNum%K;
		curFileNum=ceil(curFileNum*1.0/K);

		cout<<times<<" "<<curFileNum<<" "<<leftNum<<" "<<endl;

		for(i=1;i<curFileNum;++i)
		{
			 K_merge(getFileName( i,(times+1)),(i-1)*K+1,K*i,times );
		}
		if( leftNum!=0) K_merge(getFileName( i,(times+1)), (i-1)*K+1, (i-1)*K+leftNum ,times );
		else
		{
			K_merge(getFileName( i,(times+1)),(i-1)*K+1,K*i,times );
		}
		++times;
	}
	if(curFileNum == 0 ) return;
	else
	{
		K_merge(finalFile,1,curFileNum,times);
	}
}

int main()
{
	 srand((int)time(0));
	 time_t start=time(NULL);

//     int k= dataCut(".//data.txt", 100000, 10000000);

	 All_merge(".//Dest.txt",100);
//	 showTimeUsed(start);

//	 K_merge(".//Dest.txt");

     showTimeUsed(start);
	 return 0;
}