排序特辑：归并外排序（基础）

排序特辑：归并外排序（基础）

目录

前言

外排序

背景

概念

归并外排序

测试

---

前言

本章主要讲解：

归并外排序的 *** 作以及实现（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;
}

• 测试结果：

 

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