那篇外排摸索文章里的代码都是我一点一点修改的片段,现在有一个可以运行的完整版本。
由于自己写的快排效率稍差,所以改用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;
}
分享到:
相关推荐
10. **希尔排序**:改进版的插入排序,通过增量序列将待排序数组划分为多个子序列,分别进行插入排序,最后进行一次全序列的插入排序。C语言实现涉及增量序列的选择和子序列的排序。 每种排序算法都有其适用场景,...
在给定的资源中,"冒泡排序源代码下载"提供了冒泡排序算法的实现,这可能是用C#或Visual Basic等编程语言编写的,因为文件名包含“视窗版”,暗示这是一个用于Windows平台的程序。`.sln`文件是Visual Studio解决方案...
在这个"快速排序示例代码(JAVA版)"中,我们可以期待看到以下关键知识点: 1. **分治策略**:快速排序的核心在于将大问题分解为小问题来解决。在Java代码中,会有一个主函数作为入口,调用递归函数来执行排序过程。 ...
在这个压缩包文件中,"快排"可能包含了C语言实现快速排序的完整代码,供学习者参考和实践。通过理解并动手实现这些代码,你可以深入掌握快速排序的工作原理和C语言编程技巧,对于提升编程能力非常有帮助。
在“山东大学数据结构课程设计第一部分代码——外排序”这个项目中,学生将学习并实现这种高级排序算法。 外排序主要涉及以下几个核心知识点: 1. **大文件处理**:当数据量超过内存容量时,不能一次性将所有数据...
8. **希尔排序**:希尔排序是插入排序的改进版,通过增量序列分组进行插入排序,能更快地达到稳定状态。JAVA实现时,需要设计合适的增量序列,时间复杂度取决于增量序列,一般介于O(n)到O(n^2)之间。 9. **计数排序...
### 关于冒泡排序的完整代码 #### 一、冒泡排序简介 冒泡排序是一种简单直观的排序算法,其基本思想是通过不断地比较相邻两个元素的大小,并根据需要进行交换,来达到排序的目的。该算法的名字来源于较小的元素会...
7. **堆排序**:基于完全二叉树的堆数据结构,通过构建大顶堆或小顶堆进行排序。堆排序在原地进行,无需额外空间,但效率低于快速排序。 8. **计数排序**:非基于比较的排序,适用于整数排序,统计每个元素出现的...
堆排序利用了完全二叉树的特性,将待排序数组构造成一个大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,缩小排序范围,再调整堆。时间复杂度为O(n log n)。 8. **计数排序(Counting Sort)** 计数排序适用于非负...
C语言版归并排序算法完整代码,欢迎交流讨论。
- 张琨的《数据结构与算法分析(C++语言版)》则提供了更多实践性的指导和代码示例。 总的来说,直接插入排序是一种基础且实用的排序算法,理解其工作原理和实现方式对学习数据结构和算法非常有帮助。在实际编程中...
- 最好情况时间复杂度:O(n^2),即使数组已经是有序的,也要执行完整的比较过程。 - 平均情况时间复杂度:O(n^2)。 - 最坏情况时间复杂度:O(n^2),无论输入数组的状态如何。 - 空间复杂度:O(1)。 - 稳定性:不稳定...
《排序子系统——C语言...总结,这个C语言版的排序子系统是学习和实践排序算法的理想平台。通过阅读和理解源代码,学生不仅可以巩固C语言基础,还能深入了解各种排序算法的原理和实现,为未来的编程项目打下坚实基础。
快速排序的平均时间复杂度为O(n log n),在最坏情况下,即输入数组已经完全有序时,时间复杂度为O(n^2)。然而这种情况在实际应用中很少出现,因为快速排序通常表现出优秀的性能。空间复杂度为O(log n),这是由于递归...
堆排序利用了堆的数据结构,将待排序的数组视为完全二叉树,并保持树的性质(大顶堆或小顶堆)。首先构建堆,然后将最大元素(或最小元素)与末尾元素交换,再重新调整堆。堆排序在最坏和平均情况下都有O(n log n)的...
本文将深入探讨在C++中实现的各种排序算法,包括它们的工作原理、效率以及如何用C++代码来表达。 首先,我们来看直接插入排序。这种排序算法的工作方式类似于我们手动排列一副扑克牌,每次将一个未排序的元素插入到...
堆排序利用了完全二叉树的特性,通过构建最大堆或最小堆进行排序。其时间复杂度为O(n log n),且是原地排序,不需要额外空间。 8. **计数排序(Counting Sort)**: 计数排序是一种非基于比较的排序算法,适用于...
Java实现六种常用排序 并用多线程进行速度比较(其实意义不大) 含有代码
在VB6.0环境下,开发一个排序输出程序是一项基础但重要的编程任务,它涉及到数据处理和算法的应用。...提供的文件“VB2010-03-06-排序输出”可能包含完成以上步骤的完整源代码,供学习者参考和研究。