【数据结构与算法】数据结构初阶：排序内容加餐（二）——文件归并排序思路详解（附代码实现）

//测试排序的性能对比  
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}
	//begin和end的时间差就是
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	BubbleSort(a7, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}

#define  _CRT_SECURE_NO_WARNINGS  1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

//创建N个随机数，写到文件中
void CreatNData()
{
	//造数据
	int n = 10000000;

	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		int x = rand() + i;
		fprintf(fin, "% d\n", x);
	}

	fclose(fin);
}

int compare(const void* a, const void* b)
{
	return(*(int*)a - *(int*)b);
}

//返回实际读到的数据个数，没有数据了返回0
int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
{
	int x = 0;
	int* a = (int*)malloc(sizeof(int) * n);
	if (a == NULL)
	{
		perror("malloc error");
		return 0;
	}

	//想读取n个数据，如果遇到文件结束，应该读到j个
	int j = 0;
	for (int i = 0; i < n; i++)
	{
		if (fscanf(fout, "%d", &x) == EOF)
			break;
		
		a[j++] = x;
	}

	if (j == 0)
	{
		free(a);
		return 0;
	}

	//排序
	qsort(a, j, sizeof(int), compare);

	FILE* fin = fopen(file1, "w");
	if (fin == NULL)
	{
		free(a);
		perror("fopen error");
		return 0;
	}

	//写回file1文件
	for (int i = 0; i < j; i++)
	{
		fprintf(fin, "%d\n", a[j]);
	}

	free(a);
	fclose(fin);

	return j;
}

void MergeFile(const char* file1, const char* file2, const char* mfile)
{
	FILE* fout1 = fopen(file1, "r");
	if (fout1 == NULL)
	{
		perror("fopen error");
		return;
	}

	FILE* fout2 = fopen(file2, "r");
	if (fout2 == NULL)
	{
		perror("fopen error");
		return;
	}

	FILE* mfin = fopen(mfile, "w");
	if (mfin == NULL)
	{
		perror("fopen error");
		return;
	}

	//归并逻辑
	int x1 = 0;
	int x2 = 0;
	int ret1 = fscanf(fout1, "%d", &x1);
	int ret2 = fscanf(fout2, "%d", &x2);
	while (ret1 != EOF && ret2 != EOF)
	{
		if (x1 < x2)
		{
			fprintf(mfin, "%d\n", x1);
			ret1 = fscanf(fout1, "%d", &x1);
		}
		else
		{
			fprintf(mfin, "%d\n", x2);
			ret2 = fscanf(fout2, "%d", &x2);
		}
	}

	while (ret1 != EOF)
	{
		fprintf(mfin, "%d\n", x1);
		ret1 = fscanf(fout1, "%d", &x1);
	}
	while (ret2 != EOF)
	{
		fprintf(mfin, "%d\n", x2);
		ret2 = fscanf(fout2, "%d", &x2);
	}

	fclose(fout1);
	fclose(fout2);
	fclose(mfin);
}

int main()
{
	CreatNData();

	const char* file1 = "file1.txt";
	const char* file2 = "file1.txt";
	const char* mfile = "file1.txt";

	FILE* fout = fopen("data.txt", "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	int m = 1000000;
	ReadNDataSortToFile(fout, m, file1);
	ReadNDataSortToFile(fout, m, file2);

	while (1)
	{
		MergeFile(file1, file2, mfile);

		//删除file1和file2
		remove(file1);
		remove(file2);

		//重命名mfile为file1
		rename(mfile, file1);

		//当再去读取数据，一个都读不到，说明此时已经没有数据了
		//已经归并完成，归并结果在file1
		int n = 0;
		if ((n = ReadNDataSortToFile(fout, m, file2)) == 0)
			break;

		//if (n < 100)
		//{
		//	int x = 0;
		//}
	}
	return 0;
}