数据结构初阶(C)|归并排序的外部排序算法实现数据结构初阶(C)|算法

归并排序的外部排序

外部排序概念
场景
拓展
实现函数
- - 归并外排序主函数
  - 将传入两个文件归并入mfile
完成外排序

外部排序概念

参考：一眨眼的功夫了解什么是外部排序算法
按照内存大小，将大文件分成若干长度适当(小于内存可使用的大小)的子文件，再使用内部排序算法(快排，堆排…)对单个子文件进行排序，并将这些子文件写入辅助存储器。最后对这些子文件进行合并，直到得到一个有序的文件

场景

当待排序的文件比内存的可使用容量还大时，文件无法一次性放到内存中进行排序，需要借助于辅助存储器时，就需要用到外部排序
外排效率：取决于读写辅助存储器的次数，而归并的次数就是访问辅助存储器的次数
n路平衡归并(n为每次归并的临时子文件个数)
下图为4路平衡归并
文章图片

拓展

所以为提高效率(我们可以根据实际情况)：

增加子文件的大小以减少子文件的个数
参考：置换选择排序算法

减小归并次数
参考：多路平衡归并排序算法（多路归并排序、胜者树、败者树）

参考：最佳归并树

实现函数

这里我们准备100个随机数字模拟大文件，并将其拆分为10个文件使用如下图方式对其进行操作

文章图片

文章图片

归并外排序主函数

注意点：

文件操作函数的具体使用方式(返回值，参数等特性)

每次对文件写入10个数控制if条件i < n-1而不是i
对文件的命名如sprintf(mfile, "%s%d", mfile, i+1)每次是把mfile的名称和i+1结合起来，例如mfile原来是sub_sort0，i为0，新的mfile为sub_sort01，但是如果以多余的字符命名会出现sub_sortsub_sort012的情况

//归并外排序主函数 void MergeSortFile(const char* file) { FILE* fout = fopen(file, "r"); if (fout == NULL) {printf("fail main_fout"); exit(-1); } // int n = 10; //每个文件n个数 int a[10]; //分为10个文件夹 int i = 0; int num = 0; //用来存放每次读取的数值(假设有100个) char subfile[20]; //快排完写入的文件名 int filei = 0; //用来创建文本文件命名如：sub_sort1， sub_sort2， sub_sort3...（中的1，2，3...） //memset(a, 0, sizeof(int)*n); while (fscanf(fout, "%d\n", &num) != EOF)//从输入流fout中读入数据，存储到num中 {if (i < n-1)//每个文件10个数（i<9）防止i加到10 {a[i++] = num; //最后一次i=8赋值后i加到9 } else {a[i] = num; //每个文件10个数（i<9）防止i加到10PartSort3_right(a, 0, n - 1); //对每次分到的10个元素排序（快排前后指针法，key在最右边） sprintf(subfile, "%d", filei++); //sprintf 按 sub\\sub_sort%d 此格式 //(\\是盘符后面的\ 有两根是转义字符，防止识别不了)写入subfile FILE* fin = fopen(subfile, "w"); if (fin == NULL) {printf("fail fin_main\n"); exit(-1); } for (int i = 0; i < n; i++) {fprintf(fin, "%d\n", a[i]); //排完序写入此文件 } fclose(fin); i = 0; //i置为0 准备写到下一个文件 //memset(a, 0, sizeof(int)*n); } } //以上为拆分文件并分别快排 //以下利用互相归并到文件，实现整体有序 char mfile[100] = "01"; char file0[100] = "0"; char file1[100]; for (int i = 1; i < n; i++) {sprintf(file1, "%d", i); _MergeFile(file0, file1, mfile); strcpy(file0, mfile); sprintf(mfile, "%s%d", mfile, i+1); //注意txt问题和sub\\sub_sort的坑 } fclose(fout); }

将传入两个文件归并入mfile

注意点：

第一个循环不能按照普通的归并逻辑，因为fscanf相当于自动++，while (fscanf(fout1, "%d", &num1) != EOF && fscanf(fout2,"%d",&num2) != EOF) 会导致在写入小的一组后大的那一组也会++，读丢元素

如果后面的两个while循环直接while (fscanf(fout1, “%d”, &num1) != EOF),会导致写入的合并文件最后少一个，因为当倒数第二个数被写入后fscanf会马上读取接下来的最后一个数，马上此文件在为空了，然而在while里直接用fscanf的话就是EOF，剩下的最后一个数不会被写入合并文件

//传两个文件进行归并 void _MergeFile(const char* file1, const char* file2, const char* mfile) { int num1 = 0; int num2 = 0; FILE *fout1 = fopen(file1, "r"); if (fout1 == NULL) {printf("failed to open fout1\n"); exit(-1); } FILE *fout2 = fopen(file2, "r"); if (fout2 == NULL) {printf("failed to open fout2\n"); exit(-1); } FILE *fin= fopen(mfile, "w"); if (fin == NULL) {printf("failed to open fin\n"); exit(-1); } //这里不能按照普通的归并逻辑，因为fscanf相当于自动++， //while (fscanf(fout1, "%d", &num1) != EOF && fscanf(fout2,"%d",&num2) != EOF) 会导致在写入小的一组后大的那一组也会++，读丢元素 int ret1 = fscanf(fout1, "%d", &num1); int ret2 = fscanf(fout2,"%d",&num2); while (ret1 != EOF && ret2 != EOF) {if (num1 < num2) {fprintf(fin, "%d\n", num1); ret1 = fscanf(fout1, "%d", &num1); } else {fprintf(fin, "%d\n", num2); ret2 = fscanf(fout2, "%d", &num2); } } //注意：如果这里直接while (fscanf(fout1, "%d", &num1) != EOF),会导致写入的合并文件最后少一个， //因为当倒数第二个数被写入后fscanf会马上读取接下来的最后一个数，马上此文件在为空了， //然而在while里直接用fscanf的话就是EOF，剩下的最后一个数不会被写入合并文件 while (ret1 != EOF) {fprintf(fin, "%d\n", num1); ret1 = fscanf(fout1, "%d", &num1); } while (ret2 != EOF) {fprintf(fin, "%d\n", num2); ret2 = fscanf(fout2, "%d", &num2); } fclose(fout1); fclose(fout2); fclose(fin); }

完成外排序 【数据结构初阶(C)|归并排序的外部排序算法实现】