外排序的实现

思想
代码分析
完整代码

如果有海量数据需要排序，而在内存中放不下这么多数据，因此就不能使用内排序（直接插入排序，希尔排序，堆排序，快速排序，归并排序等等）。关于想了解这些内排序的请看这里各种排序的实现，所以我们只能使用外排序，来把我们海量数据排好序，

思想

外排序，我们需要采用归并排序的思想来实现这个过程。
在这里插入图片描述

因此我们最终思想是这样的
在这里插入图片描述

代码分析

要学会写外排序的代码，需要把文件学好，想了解文件的请看这里文件

假设文件里有100个数据
生成1-100个随机数放在文件里

#define N 100void CreteartFile(const char* filename)
{srand((unsigned int)time(NULL));//生成一个随机数1-100的文件FILE* pf = fopen(filename, "w");if (pf == NULL){perror("fopen fail");return;}for (int i = 0; i < N; ++i){fprintf(pf, "%d ", rand() % 100 + 1);}fclose(pf);}int  main()
{const char* filename = "Sort.txt";CreteartFile(filename);//外排序MerSortFile(filename);return 0;
}

把文件平均分成若干个有序的小文件

我们有一个100个数的文件
把这个文件平均分成10个小文件，每个小文件放10个数。
为了使这些小文件的数据有序，因此我们在大文件里取出数据，放在数组a中，只要数组a里的数据达到10个。就对数组a使用快排（假设内存可以一次放得下这么数据），直到取完文件中的数据。

//外排序
void MerSortFile(const char* filename)
{//取数据，把一个文件分成若干个有序的小文件FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}int a[10] = { 0 };int value = 0;int i = 0;int n = 10;//存放小文件名称char fsubename[10] = { 0 };int fnumeber = 0;//从文件中取出数据while (fscanf(fout, "%d", &value) != EOF){//一个小文件放10个数据if (i < n-1){a[i++] = value;}else{//这里是特殊处理，下面画图有解释a[i] = value;//对a数组排序QuickSort(a, 0, n - 1);//创建小文件，并将a写到小文件里sprintf(fsubename, "%d.txt", ++fnumeber);FILE* fin = fopen(fsubename, "w");if (fin == NULL){perror("fopen fail");return;}//写数据for (int i = 0; i < n; ++i){fprintf(fin, "%d ", a[i]);}fclose(fin);i = 0;}}fclose(fout);
}

在这里插入图片描述
两两归并小文件，直到归并成一个文件

//外排序
void MerSortFile(const char* filename)
{//取数据，把一个文件分成若干个有序的小文件FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}int a[10] = { 0 };int value = 0;int i = 0;int n = 10;char fsubename[10] = { 0 };int fnumeber = 0;while (fscanf(fout, "%d", &value) != EOF){//一个小文件放10个数据if (i < n-1){a[i++] = value;}else{a[i] = value;//对a数组排序QuickSort(a, 0, n - 1);//创建小文件，并将a写到小文件里sprintf(fsubename, "%d.txt", ++fnumeber);FILE* fin = fopen(fsubename, "w");if (fin == NULL){perror("fopen fail");return;}//写数据for (int i = 0; i < n; ++i){fprintf(fin, "%d ", a[i]);}fclose(fin);i = 0;}}//归并小文件,直到整体归成一个有序的完整文件//这一块逻辑看下图分析char mfile[20] = "12";char file1[20] = "1.txt";char file2[20] = { 0 };for (int i = 2; i <= n; ++i){sprintf(file2, "%d.txt", i);_MergerFile(mfile, file1, file2);//迭代，file1存储mfile名strcpy(file1, mfile);//mfile存储下一次两个文件要归并在一起的文件名sprintf(mfile, "%s%d", mfile, i+1);}fclose(fout);
}

在这里插入图片描述
两个小文件归并过程

void _MergerFile(const char* mfile,const char* file1,const char* file2)
{FILE* fin = fopen(mfile, "w");if (fin == NULL){perror("fopen fail");return;}FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen fail");return;}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen fail");return;}int num1 = 0;int num2 = 0;
//这里也是对文件指针的特殊处理，看下图int ret1 = fscanf(fout1, "%d", &num1);int ret2 = fscanf(fout2, "%d", &num2);while (ret1 != EOF && ret2 != EOF){if (num1 < num2){fprintf(fin, "%d ", num1);ret1= fscanf(fout1, "%d", &num1);}else{fprintf(fin, "%d ", num2);ret2 = fscanf(fout2, "%d", &num2);}}while (ret1 != EOF){fprintf(fin, "%d ", num1);ret1 = fscanf(fout1, "%d", &num1);}while (ret2 != EOF){fprintf(fin, "%d ", num2);ret2 = fscanf(fout2, "%d", &num2);}fclose(fin);fclose(fout1);fclose(fout2);}

在这里插入图片描述

完整代码

//合并小文件
void _MergerFile(const char* mfile,const char* file1,const char* file2)
{FILE* fin = fopen(mfile, "w");if (fin == NULL){perror("fopen fail");return;}FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen fail");return;}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen fail");return;}int num1 = 0;int num2 = 0;int ret1 = fscanf(fout1, "%d", &num1);int ret2 = fscanf(fout2, "%d", &num2);while (ret1 != EOF && ret2 != EOF){if (num1 < num2){fprintf(fin, "%d ", num1);ret1= fscanf(fout1, "%d", &num1);}else{fprintf(fin, "%d ", num2);ret2 = fscanf(fout2, "%d", &num2);}}while (ret1 != EOF){fprintf(fin, "%d ", num1);ret1 = fscanf(fout1, "%d", &num1);}while (ret2 != EOF){fprintf(fin, "%d ", num2);ret2 = fscanf(fout2, "%d", &num2);}fclose(fin);fclose(fout1);fclose(fout2);}//外排序
void MerSortFile(const char* filename)
{//取数据，把一个文件分成若干个有序的小文件FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}int a[10] = { 0 };int value = 0;int i = 0;int n = 10;char fsubename[10] = { 0 };int fnumeber = 0;while (fscanf(fout, "%d", &value) != EOF){//一个小文件放10个数据if (i < n-1){a[i++] = value;}else{a[i] = value;//对a数组排序QuickSort(a, 0, n - 1);//创建小文件，并将a写到小文件里sprintf(fsubename, "%d.txt", ++fnumeber);FILE* fin = fopen(fsubename, "w");if (fin == NULL){perror("fopen fail");return;}//写数据for (int i = 0; i < n; ++i){fprintf(fin, "%d ", a[i]);}fclose(fin);i = 0;}}//归并小文件,直到整体归成一个有序的完整文件char mfile[20] = "12";char file1[20] = "1.txt";char file2[20] = { 0 };for (int i = 2; i <= n; ++i){sprintf(file2, "%d.txt", i);_MergerFile(mfile, file1, file2);strcpy(file1, mfile);sprintf(mfile, "%s%d", mfile, i+1);}fclose(fout);
}