【算法】外排序

1 外排序

众所周知，一些最经典的排序算法如：冒泡法排序、插入排序、希尔排序、快速排序、选择排序等等，它们都是在内存中对数据进行排序。可是如果现在需要对海量个数据进行排序，这海量个数据在内存无法存下，只能放在文件当中，这又要如何解决呢？答案就是用我们的归并排序！

1.1外排序思想

假设我们需要排序N个数据（内存无法存下，只能放在文件中），而内存中最多存放a个数据；那我们就将这个N个数据分成n等份，直到每份的数量小于a为止。

为了直观地演示，我们在文件中放100个数据（模拟海量数据），假定内存中最多存放10个数据，那么我们将文件中的数据分为10份，每份进入内存使用快速排序排序完成后，在将排好的10份数据进行归并：1与2归并，生成12,12再与3归并，生成123，123再与4归并，生成1234…以此类推直到所有文件归并完成。

1.2外排序代码实现

首先，我们先来看一下单趟的文件归并：（类似于合并两个有序数组）

/*
file1：文件1	file2：文件2	mfile：文件1文件2归并后的文件
*/
void _MergeFile(const char* file1, const char* file2, const char* mfile)//归并两个文件
{
	FILE* fout1 = fopen(file1, "r");
	if (fout1 == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	FILE* fout2 = fopen(file2, "r");
	if (fout2 == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	FILE* fin = fopen(mfile, "w");
	if (fin == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	
	int num1, num2;
	int ret1 = fscanf(fout1, "%d\n", &num1);//从fout1文件中读取%d\n，然后将%d放入到num1中
	int ret2 = fscanf(fout2, "%d\n", &num2);
	while (ret1 != EOF && ret2 != EOF)//以下操作类似于合并两个有序数组
	{
		if (num1 < num2)
		{
			fprintf(fin, "%d\n", num1);
			ret1 = fscanf(fout1, "%d\n", &num1);
		}
		else
		{
			fprintf(fin, "%d\n", num2);
			ret2 = fscanf(fout2, "%d\n", &num2);
		}
	}

	while (ret1 != EOF)
	{
		fprintf(fin, "%d\n", num1);
		ret1 = fscanf(fout1, "%d\n", &num1);
	}

	while (ret2 != EOF)
	{
		fprintf(fin, "%d\n", num2);
		ret2 = fscanf(fout2, "%d\n", &num2);
	}

	fclose(fout1);
	fclose(fout2);
	fclose(fin);
}

下面为整体代码：

void MergeSortFile(const char* file)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	// 分割成一段一段数据，内存排序后写到，小文件，
	int n = 10;
	int a[10];
	int i = 0;
	int num = 0;
	char subfile[20];
	int filei = 1;

	memset(a, 0, sizeof(int) * n);
	while (fscanf(fout, "%d\n", &num) != EOF)
	{
		if (i < n - 1)
		{
			a[i++] = num;
		}
		else
		{
			a[i] = num;
			QuickSort(a, 0, n - 1);
			sprintf(subfile, "%d", filei++);
			FILE* fin = fopen(subfile, "w");
			if (fin == NULL)
			{
				printf("打开文件失败\n");
				exit(-1);
			}
			for (int j = 0; j < n; j++)
			{
				fprintf(fin, "%d\n", a[j]);
			}
			fclose(fin);

			i = 0;
			memset(a, 0, sizeof(int) * n);
		}
	}

	// 利用互相归并到文件，实现整体有序
	char mfile[100] = "12";
	char file1[100] = "1";
	char file2[100] = "2";
	for (int i = 2; i <= n; ++i)
	{
		// 读取file1和file2,进行归并出mfile
		_MergeFile(file1, file2, mfile);

		strcpy(file1, mfile);
		sprintf(file2, "%d", i + 1);
		sprintf(mfile, "%s%d", mfile, i + 1);
	}

	printf("%s文件排序成功\n", file);
	fclose(fout);
}

int main()
{
	MergeSortFile("SortData.txt");

	return 0;
}