`
ZeaLoVe
  • 浏览: 91598 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

外排序完整版代码

 
阅读更多

 

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

   由于自己写的快排效率稍差,所以改用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;
}
分享到:
评论

相关推荐

    C语言几种排序代码

    10. **希尔排序**:改进版的插入排序,通过增量序列将待排序数组划分为多个子序列,分别进行插入排序,最后进行一次全序列的插入排序。C语言实现涉及增量序列的选择和子序列的排序。 每种排序算法都有其适用场景,...

    冒泡排序源代码下载 冒泡排序源代码下载

    在给定的资源中,"冒泡排序源代码下载"提供了冒泡排序算法的实现,这可能是用C#或Visual Basic等编程语言编写的,因为文件名包含“视窗版”,暗示这是一个用于Windows平台的程序。`.sln`文件是Visual Studio解决方案...

    快速排序示例代码(JAVA版)

    在这个"快速排序示例代码(JAVA版)"中,我们可以期待看到以下关键知识点: 1. **分治策略**:快速排序的核心在于将大问题分解为小问题来解决。在Java代码中,会有一个主函数作为入口,调用递归函数来执行排序过程。 ...

    数据结构快速排序完整版

    在这个压缩包文件中,"快排"可能包含了C语言实现快速排序的完整代码,供学习者参考和实践。通过理解并动手实现这些代码,你可以深入掌握快速排序的工作原理和C语言编程技巧,对于提升编程能力非常有帮助。

    山东大学数据结构课程设计第一部分代码——外排序

    在“山东大学数据结构课程设计第一部分代码——外排序”这个项目中,学生将学习并实现这种高级排序算法。 外排序主要涉及以下几个核心知识点: 1. **大文件处理**:当数据量超过内存容量时,不能一次性将所有数据...

    各种排序代码的JAVA实现

    8. **希尔排序**:希尔排序是插入排序的改进版,通过增量序列分组进行插入排序,能更快地达到稳定状态。JAVA实现时,需要设计合适的增量序列,时间复杂度取决于增量序列,一般介于O(n)到O(n^2)之间。 9. **计数排序...

    关于冒泡排序的完整代码

    ### 关于冒泡排序的完整代码 #### 一、冒泡排序简介 冒泡排序是一种简单直观的排序算法,其基本思想是通过不断地比较相邻两个元素的大小,并根据需要进行交换,来达到排序的目的。该算法的名字来源于较小的元素会...

    Java各种排序算法代码.

    7. **堆排序**:基于完全二叉树的堆数据结构,通过构建大顶堆或小顶堆进行排序。堆排序在原地进行,无需额外空间,但效率低于快速排序。 8. **计数排序**:非基于比较的排序,适用于整数排序,统计每个元素出现的...

    各种排序算法源代码

    堆排序利用了完全二叉树的特性,将待排序数组构造成一个大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,缩小排序范围,再调整堆。时间复杂度为O(n log n)。 8. **计数排序(Counting Sort)** 计数排序适用于非负...

    归并排序 C语言版

    C语言版归并排序算法完整代码,欢迎交流讨论。

    直接插入排序C++代码 VS实现

    - 张琨的《数据结构与算法分析(C++语言版)》则提供了更多实践性的指导和代码示例。 总的来说,直接插入排序是一种基础且实用的排序算法,理解其工作原理和实现方式对学习数据结构和算法非常有帮助。在实际编程中...

    Java排序算法代码

    - 最好情况时间复杂度:O(n^2),即使数组已经是有序的,也要执行完整的比较过程。 - 平均情况时间复杂度:O(n^2)。 - 最坏情况时间复杂度:O(n^2),无论输入数组的状态如何。 - 空间复杂度:O(1)。 - 稳定性:不稳定...

    排序子系统 C语言版

    《排序子系统——C语言...总结,这个C语言版的排序子系统是学习和实践排序算法的理想平台。通过阅读和理解源代码,学生不仅可以巩固C语言基础,还能深入了解各种排序算法的原理和实现,为未来的编程项目打下坚实基础。

    快速排序标准代码

    快速排序的平均时间复杂度为O(n log n),在最坏情况下,即输入数组已经完全有序时,时间复杂度为O(n^2)。然而这种情况在实际应用中很少出现,因为快速排序通常表现出优秀的性能。空间复杂度为O(log n),这是由于递归...

    内部排序算法分析与代码算法

    堆排序利用了堆的数据结构,将待排序的数组视为完全二叉树,并保持树的性质(大顶堆或小顶堆)。首先构建堆,然后将最大元素(或最小元素)与末尾元素交换,再重新调整堆。堆排序在最坏和平均情况下都有O(n log n)的...

    各种排序算法c++源代码

    本文将深入探讨在C++中实现的各种排序算法,包括它们的工作原理、效率以及如何用C++代码来表达。 首先,我们来看直接插入排序。这种排序算法的工作方式类似于我们手动排列一副扑克牌,每次将一个未排序的元素插入到...

    C/C++数据结构_随机10000个数:排序~8大排序代码集.rar

    堆排序利用了完全二叉树的特性,通过构建最大堆或最小堆进行排序。其时间复杂度为O(n log n),且是原地排序,不需要额外空间。 8. **计数排序(Counting Sort)**: 计数排序是一种非基于比较的排序算法,适用于...

    Java实现六种常用排序(含源代码)

    Java实现六种常用排序 并用多线程进行速度比较(其实意义不大) 含有代码

    排序输出程序(VB6.0源代码编写)

    在VB6.0环境下,开发一个排序输出程序是一项基础但重要的编程任务,它涉及到数据处理和算法的应用。...提供的文件“VB2010-03-06-排序输出”可能包含完成以上步骤的完整源代码,供学习者参考和研究。

Global site tag (gtag.js) - Google Analytics