排序特辑:归并外排序(基础)

排序特辑:归并外排序(基础),第1张

排序特辑:归并排序(基础)

目录

前言

外排

背景

概念

归并外排

测试


前言

本章主要讲解:

归并外排序的操作以及实现(C语言)

注:本章需要用到文件操作的知识,如果有问题,可以先浏览学习一下文件操作的知识:⭐️ C语言进阶 ⭐️ 文件操作超详解【 建议关注+收藏 】

外排序 背景

  一般提到排序都是指内排序,比如快速排序,堆排序,归并排序等。所谓内排序就是可以在内存中完成的排序,内存的访问速度大约是磁盘的25万倍,如果可以的话在内存中排序是非常快的。但对于大量数据来说,数据太大而无法全部都将数据加载到内存中,这时候就需要外排序。

概念

  外排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

归并外排序

在整体外排序中用归并的思想实现

  • 排序策略
  1. 首先将整体大文件进行划分成多个内存能全加载的临时文件
  2. 再逐个对划分好的临时文件进行加载到内存,并进行内排序(可以使用高效的排序,建议快排)
  3. 排序好后对两两文件进行归并操作
  • 具体归并细节:排升序

  分别读取两两文件中的一个数据,进行比较,将小的数据输出到新的临时文件中,再对小数据的文件进行读取新的数据,以此循环直到归并完毕

  • 图示过程:

  • 实现代码:
//归并外排序
void Mergefile(const char* fin1, const char* fin2, const char* fmerge)
{
	//以写入的方式创建合并后的新临时文件
	FILE* fout = fopen(fmerge, "w");
	if (fout == NULL)
	{
		perror("fopen fout failn");
		exit(-1);
	}
	//以读取的方式打开合并子文件
	FILE* file1 = fopen(fin1, "r");
	if (file1 == NULL)
	{
		perror("fopen file1 failn");
		exit(-1);
	}
	FILE* file2 = fopen(fin2, "r");
	if (file2 == NULL)
	{
		perror("fopen file2 failn");
		exit(-1);
	}
	//归并排序文件数据
	int num1, num2;
	int ret1 = fscanf(file1, "%dn", &num1);//文件成功读取,读取指针则自动往后走
	int ret2 = fscanf(file2, "%dn", &num2);//所以保存返回结果,比较数据写入后再读取文件
	while (ret1 != EOF && ret2 != EOF)
	{
		if (num1 < num2)
		{
			//写入数据并读取下一个数据
			fprintf(fout, "%dn", num1);
			ret1 = fscanf(file1, "%dn", &num1);
		}
		else
		{
			fprintf(fout, "%dn", num2);
			ret2 = fscanf(file2, "%dn", &num2);
		}
	}
	while (ret1 != EOF)
	{
		fprintf(fout, "%dn", num1);
		ret1 = fscanf(file1, "%dn", &num1);
	}
	while (ret2 != EOF)
	{
		fprintf(fout, "%dn", num2);
		ret2 = fscanf(file2, "%dn", &num2);
	}
	fclose(file1);
	fclose(file2);
	fclose(fout);
}

void MergeSortFile(const char* file, int N, int Num)
{
	//以读取的方式打开数据文件
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen failn");
		exit(-1);
	}
	//开辟额外空间来接收数据
	int* arr = malloc(sizeof(int) * Num);
	if (arr == NULL)
	{
		perror("malloc failn");
		exit(-1);
	}
	//把大文件划分成小文件,并排序
	char subfile[100];//小文件名
	int filei = 1, i=0, num;
	while(fscanf(fout, "%dn", &num) != EOF)
	{
		if (i < Num - 1)
		{
			arr[i++] = num;//载入内存
		}
		else//再入够数据进行排序,对排序好的数据输出到临时文件中
		{
			arr[i] = num;
			QuickSort(arr, 0, Num-1);//排序
			//排好后写入文件
			sprintf(subfile, "Sortedfile%d", filei++);//创建修改小文件名
			FILE* fin = fopen(subfile, "w");//以写入的方式创建小文件
			if (fin == NULL)//文件开辟失败
			{
				perror("fopen subfile failn");
				exit(-1);
			}
            //输出到文件中
			for (int j = 0; j < Num; j++)
			{
				fprintf(fin, "%dn", arr[j]);//写入排好的数据
			}
			fclose(fin);
			i = 0;//更新记录读取数据的个数变量
		}
	}
	//开始进行合并数据文件
	char fin1[100] = "Sortedfile1";
	char fin2[100] = "Sortedfile2";
	char fmerge[100] = "Sortedfile12";
	for (i = 1; i < N; i++)
	{
		//归并文件
		Mergefile(fin1, fin2, fmerge);
		//更替文件名
		strcpy(fin1, fmerge);
		sprintf(fin2, "Sortedfile%d", i + 2);
		sprintf(fmerge, "%s%d", fmerge, i + 2);
	}
	fclose(fout);
	free(arr);
}
测试
  • 测试代码:
int main()
{
	//获取随机种子
	srand(time(0));
	//创建待排序数据文件
	char file[100] = "datafile.txt";
	FILE* data = fopen(file, "w");
	if (data == NULL)
	{
		perror("fopen failn");
		exit(-1);
	}
	//将随机数写进写入文件
	const n = 10, num = 5000;
	for (int i = 0; i < n * num; i++)
	{
		fprintf(data, "%dn", rand());
	}
	fclose(data);
	//排序
	MergeSortFile(file, n, num);

	return 0;
}
  • 测试结果:

 

 看来归并外排序实现的还是非常成功的!!

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/zaji/5636669.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-12-16
下一篇2022-12-16

随机推荐

  • ppt如何制作双层饼图_饼图的高级玩法

    前面我们分享了EXCEL柱形图、旋风图(非字型图表)的制作和美化方法,今天分享双层饼图的制作方法,需要的小伙伴快来收藏!一、双层饼图效果二、双层饼图的制作步骤案例:根据下图中的数据制作双层饼图第一步:创建城市销量饼图。选中B3:B11

    2022-12-29
    2100
  • 自己的房子可以让别人落户吗

    现在在一个城市落户还是比较麻烦的事情,要么就是公共户口,要么就是自己买房后落入自己的户口中。那么, 自己的房子可以让别人落户吗?让别人落户有什么风险?一起来看看学百科带来的详细介绍吧!自己的房子可以让别人落户吗自己的房子可以让别人落户。但是

    2022-12-29
    2600
  • 牛肉馅包子放啥菜绝配

    包子的口味比较丰富,牛肉馅就是其中比较受欢迎的一种包子,很多人都会自己在家包牛肉包子吃。牛肉包子的做法比较多,可以加各种各样的食材配菜,比如白菜、白萝卜以及香菇等,搭配在一起营养又美味。牛肉馅包子用啥菜好吃1.白菜白菜富含水分,味道鲜甜。切

    2022-12-29
    1900
  • 玉竹淮山煲汤可以吗 玉竹淮山如何煲汤。

    导读:玉竹淮山煲汤可以吗?下面一起来看看吧。1、玉竹淮山可以煲汤。2、先将淮山、玉竹放入煲中,加入两汤碗清水,用猛火烧滚后,放入已洗净的白鸽和陈皮,改用慢火继续1、玉竹淮山可以煲汤。2、先将淮山、玉竹放入煲中,加入两汤碗清水,用猛火烧滚后,

    2022-12-29
    1900
  • 世界最名贵的手表_世界名表排名及价格大全

    如果有一个词来形容奢侈手表的话,那就是昂贵。世界上最昂贵的钟表都是价值数百万美元的作品,它们的存在理由似乎就是打破世界纪录,吸引顶级爱好者的眼球,鼓励百万富翁、亿万富翁、王室成员和好莱坞一线明星掏空口袋。这些手表来自世界上最名贵的手表品牌

    2022-12-29
    1400
  • 三层实木地板的优缺点 三层实木地板的优缺点是什么

    导读:三层实木地板的优缺点?下面小编为大家整理介绍。1、质量稳定:基材是使用多层实木单板制作而成的,而内部结构一般都是以纵横交错的方式叠压在一起的,所以即使木地板受潮了1、质量稳定:基材是使用多层实木单板制作而成的,而内部结构一般都是以纵横

    2022-12-29
    1600
  • 有衣帽间了主卧还需要柜子吗 有衣帽间主卧需要装柜子吗

    导读:有衣帽间了主卧还需要柜子吗?下面小编为大家整理介绍。1、有独立衣帽间,卧室还需不需要衣柜是因人而异的。2、如果空间比较大,且主卧比较空旷的话,还是可以加柜子的,看起来比1、有独立衣帽间,卧室还需不需要衣柜是因人而异的。2、如果空间比较

    2022-12-29
    1400
  • 翡翠为什么带着要飘花呢 翡翠带着要飘花的原因

    导读:翡翠为什么带着要飘花呢?下面一起来看看吧。1、翡翠带着飘花是由于翡翠在形成过程中,致色离子没有均匀地分布在翡翠各处。2、有的翡翠,颜色会呈丝带状分布在底子上,1、翡翠带着飘花是由于翡翠在形成过程中,致色离子没有均匀地分布在翡翠各处。2

    2022-12-29
    2200
  • 一楼门市取暖可以报停吗(新楼取暖费可以报停吗)

    眼见着天气日益的变冷,很多地方都开始收取取暖费,为冬季供暖提前做准备,但由于供暖费一次性交的蛮多,且很多人都不住,所以一楼门市取暖可以报停吗成了很多友友好奇的,一起看看取暖费一层不能报停怎么办。一楼门市取暖可以报停吗看地方。对于一楼门市取暖

    2022-12-29
    2500

发表评论

登录后才能评论

评论列表(0条)

    保存