前言
本章主要讲解：
归并外排序的操作以及实现（C语言）
注：本章需要用到文件操作的知识，如果有问题，可以先浏览学习一下文件操作的知识：⭐️ C语言进阶 ⭐️ 文件操作超详解【 建议关注+收藏 】
外排序
背景
一般提到排序都是指内排序，比如快速排序，堆排序，归并排序等。所谓内排序就是可以在内存中完成的排序，内存的访问速度大约是磁盘的25万倍，如果可以的话在内存中排序是非常快的。但对于大量数据来说，数据太大而无法全部都将数据加载到内存中，这时候就需要外排序。
概念
外排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
归并外排序
在整体外排序中用归并的思想实现
排序策略
首先将整体大文件进行划分成多个内存能全加载的临时文件
再逐个对划分好的临时文件进行加载到内存，并进行内排序（可以使用高效的排序，建议快排）
排序好后对两两文件进行归并操作
具体归并细节：排升序
分别读取两两文件中的一个数据，进行比较，将小的数据输出到新的临时文件中，再对小数据的文件进行读取新的数据，以此循环直到归并完毕
图示过程：
实现代码：
//归并外排序 void Mergefile(const char* fin1, const char* fin2, const char* fmerge) { //以写入的方式创建合并后的新临时文件 FILE* fout = fopen(fmerge, "w"); if (fout == NULL) { perror("fopen fout fail\n"); exit(-1); } //以读取的方式打开合并子文件 FILE* file1 = fopen(fin1, "r"); if (file1 == NULL) { perror("fopen file1 fail\n"); exit(-1); } FILE* file2 = fopen(fin2, "r"); if (file2 == NULL) { perror("fopen file2 fail\n"); exit(-1); } //归并排序文件数据 int num1, num2; int ret1 = fscanf(file1, "%d\n", &num1);//文件成功读取，读取指针则自动往后走 int ret2 = fscanf(file2, "%d\n", &num2);//所以保存返回结果，比较数据写入后再读取文件 while (ret1 != EOF && ret2 != EOF) { if (num1 < num2) { //写入数据并读取下一个数据 fprintf(fout, "%d\n", num1); ret1 = fscanf(file1, "%d\n", &num1); } else { fprintf(fout, "%d\n", num2); ret2 = fscanf(file2, "%d\n", &num2); } } while (ret1 != EOF) { fprintf(fout, "%d\n", num1); ret1 = fscanf(file1, "%d\n", &num1); } while (ret2 != EOF) { fprintf(fout, "%d\n", num2); ret2 = fscanf(file2, "%d\n", &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 fail\n"); exit(-1); } //开辟额外空间来接收数据 int* arr = malloc(sizeof(int) * Num); if (arr == NULL) { perror("malloc fail\n"); exit(-1); } //把大文件划分成小文件，并排序 char subfile[100];//小文件名 int filei = 1, i=0, num; while(fscanf(fout, "%d\n", &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 fail\n"); exit(-1); } //输出到文件中 for (int j = 0; j < Num; j++) { fprintf(fin, "%d\n", 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 fail\n"); exit(-1); } //将随机数写进写入文件 const n = 10, num = 5000; for (int i = 0; i < n * num; i++) { fprintf(data, "%d\n", rand()); } fclose(data); //排序 MergeSortFile(file, n, num); return 0; }
测试结果：
看来归并外排序实现的还是非常成功的！！
