首页 计算机科学 数据结构笔记

该系列为本人的学习笔记，主要由本人整理书写而成。部分内容来自教材、视频课程等，不能保证完全原创性。

萌新的学习笔记，写错了恳请斧正。

# 外排序（外部排序）

当数据量非常庞大以至于无法全部写入内存时，我们应该怎么排序这些数据呢？

这时，就要学会直接进行在外存中排序，也就是外部排序。

外排序不是一种独立的排序算法，还是要依赖于之前的那些排序方式。

其基本思想是这样的：

  • 将庞大的数据拆分为一个一个子文件，使得每一个子文件的数据量在内存排序可承受的范围内。
  • 将每一个文件进行正常的排序，可以选用之前学的任何排序方法。
  • 将排序好的文件再进行归并，最终合成为包含有序的所有数据的文件。

看起来不是很复杂，但是归并部分还是很有东西的。下面我们逐步讲解：

# 文件拆分并排序

这并不复杂，比方说我们将文件拆分为 splitCount 个：

void FileSort(const char* filename, int splitCount)
{
	clock_t start = clock();
	// 分割文件
	FILE* fp = fopen(filename, "r");
	if (fp == NULL)
	{
		perror("fail to open");
		exit(EXIT_FAILURE);
	}
	int* num = (int*)malloc(sizeof(int) * N / splitCount);	// 存放每个分割文件的数据
	int iNum = 0;	//num 数组的下标
	int iFile = 0;	// 分割文件的下标
	int n = 0;	// 读取的数据
	char splitFileName[50] = { 0 };	// 分割文件名
	while (fscanf(fp, "%d", &n) != EOF)
	{
		if (iNum < N / splitCount - 1)
		{
			num[iNum++] = n;
		}
		else
		{
			num[iNum] = n;
			// 排序
			HeapSort(num, N / splitCount);
			// 写入文件
			sprintf(splitFileName, "SubSort\\sort_split%d.txt", iFile++);
			FILE* splitFile = fopen(splitFileName, "w");
			if (splitFile == NULL)
			{
				perror("fail to open");
				exit(EXIT_FAILURE);
			}
			for (int i = 0; i < N / splitCount; i++)
			{
				fprintf(splitFile, "%d\n", num[i]);
			}
			fclose(splitFile);
			printf("已分割第%d个文件，总共需分割%d个文件。\n", iFile, splitCount);
			iNum = 0;
		}
	}
	// 归并文件
    // 这里插入归并文件的代码
	// 关闭文件
	fclose(fp);
	clock_t end = clock();
	printf("排序完成，共%d个数据，分割为%d个文件，归并为1个文件。\n", N, splitCount);
	printf("耗时：%f秒。\n", (double)(end - start) / CLOCKS_PER_SEC);
}
# 归并文件
这是重点也是最复杂的地方。
# 两个文件归并
我们知道两个排序文件归并的方法：两边一起读取，一直对比两边读取的数，不断取小写入输出文件即可。
void MergeFile(char* file1, char* file2, char* mergeFileName)
{
	FILE* fp1 = fopen(file1, "r");
	FILE* fp2 = fopen(file2, "r");
	if (fp1 == NULL)
	{
		perror("fail to open");
		exit(EXIT_FAILURE);
	}
	if (fp2 == NULL)
	{
		perror("fail to open");
		exit(EXIT_FAILURE);
	}
	FILE* fin = fopen("tmp.txt", "w");
	if (fin == NULL)
	{
		perror("fail to open");
		exit(EXIT_FAILURE);
	}
	int n1, n2;
	int ret1 = fscanf(fp1, "%d", &n1);
	int ret2 = fscanf(fp2, "%d", &n2);
	while (ret1 != EOF && ret2 != EOF)
	{
		if (n1 < n2)
		{
			fprintf(fin, "%d\n", n1);
			ret1 = fscanf(fp1, "%d", &n1);
		}
		else
		{
			fprintf(fin, "%d\n", n2);
			ret2 = fscanf(fp2, "%d", &n2);
		}
	}
	while (fscanf(fp1, "%d", &n1) != EOF)
	{
		fprintf(fin, "%d\n", n1);
	}
	while (fscanf(fp2, "%d", &n2) != EOF)
	{
		fprintf(fin, "%d\n", n2);
	}
	fclose(fp1);
	fclose(fp2);
	fclose(fin);
	remove(file1);
	remove(file2);
	rename("tmp.txt", mergeFileName);
}
注意：这里我们先写入数据至 tmp.txt 中，最后在将其改名为 mergeFileName 是为了防止 mergeFileName 就是 file1 或者 file2 的情况（也即直接把 file2 归并到 file1 中而不创建新的文件，或者反过来）。
# 多文件归并
但是我们往往不仅仅要把数据切分为两个，而是几十个上百个。这时我们就需要使用多文件归并的方法。
  1. 直接逐个归并
    这是最容易理解也是最差的方法。就是把拆分文件 1 和拆分文件 2 归并，结果再和拆分文件 3 归并，结果再和拆分文件 4 归并…… 最终得到完整的归并文件。
    傻子都能看出来这个方法的不靠谱，但是我们还是将代码贴出来：
    // 归并文件，这段代码填入上方 FileSort 函数中归并的留空位置
    char* mergeFileName = "sort_merge.txt";
    char file1[50] = "SubSort\\sort_split0.txt", file2[50] = {0};
    for (int i = 1; i < splitCount; i++)
    {
    	sprintf(file2, "SubSort\\sort_split%d.txt", i);
    	MergeFile(file1, file2, mergeFileName);
    	strcpy(file1, mergeFileName);
    	printf("已归并%d个文件，总共需归并%d个文件。\n", i + 1, splitCount);
    }
    这个方法是真的不靠谱，一亿个数据半小时还没归并完。
  2. 分治归并
    就是不断地两两分组归并，比方说 9 至 16 个文件归并成 5 至 8 个，5 至 8 个归并位 3 至 4 个，再归并为 2 个，最后合成完整的排序后文件。
    // 分治归并文件，这段代码填入上方 FileSort 函数中归并的留空位置
    MergeFileR(0, splitCount - 1);
    remove("SubSort\\sort_split0.txt");
    其中 MergeFileR 的定义如下：
    void MergeFileR(int left, int right)
    {
    	if (left >= right)
    	{
    		return;
    	}
    	int mid = (left + right) / 2;
    	// 递归归并
    	MergeFileR(left, mid);
    	MergeFileR(mid + 1, right);
    	// 归并
    	char file1[50] = { 0 }, file2[50] = { 0 }, mergeFileName[50] = { 0 };
    	sprintf(file1, "SubSort\\sort_split%d.txt", left);
    	sprintf(file2, "SubSort\\sort_split%d.txt", mid + 1);
    	sprintf(mergeFileName, "SubSort\\sort_split%d.txt", left);
    	MergeFile(file1, file2, mergeFileName);
    	printf("已归并%d与%d文件至%d。\n", left, mid + 1, left);
    }
    这个方法要靠谱一点，测试如下：
    测试
# 优化
进一步优化可以将基础操作从两个文件归并变成 3 个文件归并或者更多，这样分治时就是 3 合一或者更多。这样多路归并会增加内存开销和内部时间开销，但是会大大减少外部读写的开销。
更进一步优化可以引入败者树、最佳归并树等，我还不会。