【数据结构初阶】--文件归并排序

技术文档

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言：在前面我们完成了大部分常见排序算法的实现，今天这篇博客和之前的快速排序进阶一样，属于特别篇，大家可以选择性的看。如果前面的知识点都掌握的不错的话，可以了解一下这个文件的归并排序

文件归并排序

什么是文件归并排序：

文件排序的实现思路：

代码实现：

文件归并排序

在日常编程中，我们经常需要对数据进行排序，但当数据量超过内存容量时，普通的内存排序算法就显得力不从心了。文件归并排序（External Merge Sort）正是解决这一问题的经典方案，它能高效处理超出内存限制的大型数据排序。博主将详细给介绍如何用C语言实现文件归并排序，从原理到代码一步到位。

什么是文件归并排序：

文件归并排序属于外部排序算法，核心思想是分而治之：

1. 将大型文件分割成多个能被内存容纳的小文件
2. 用内存排序算法（如快速排序）对每个小文件排序
3. 逐步合并这些有序小文件，最终得到完整的有序大文件

这种方式突破了内存容量限制，特别适合处理GB级甚至更大的数据集。

文件排序的实现思路：

1. 分割文件：

设定内存缓冲区大小（如1MB），每次从原文件读取缓冲区大小的数据
对缓冲区数据进行内存排序（如qsort）
将排序后的缓冲区数据写入临时小文件
重复上述步骤，直到原文件所有数据处理完毕

2. 合并文件：

采用\"两两归并\"策略，每次合并两个有序小文件为一个更大的有序文件
若小文件数量为奇数，最后一个文件直接进入下一轮合并
重复合并过程，直到最终只剩一个文件

3.清理合并完成后删除的文件

大致过程：

1.读取n个值排序后写到file1，再读取n个值排序后写到file2
2.file1和file2利用归并排序的思想，依次读取比较，取小的尾插到mfile，mfile归并为一个有序文件
3.将file1和file2删掉，mfile重命名为file1再次读取n个数据排序后写到file2
4.继续走file1和fie2归并，重复步骤2，直到文件中无法读出数据。最后归并出的有序数据放到了file1中

如图所示：

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1#include#include#include// 创建N个随机数，写到文件中void CreateNDate(){ // 造数据 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);}// 返回实际读到的数据个数，没有数据了，返回0int 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[i]); } 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(){ CreateNDate(); const char* file1 = \"file1.txt\"; const char* file2 = \"file2.txt\"; const char* mfile = \"mfile.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;}

--大家感兴趣的话可以把代码拿着自己去测试一下，建议从少数据开始观察，这样更明显一点

往期回顾：

【数据结构初阶】--排序(一)：直接插入排序，希尔排序

【数据结构初阶】--排序(二)--直接选择排序，堆排序

【数据结构初阶】--排序(三)：冒泡排序，快速排序

【数据结构初阶】--排序(四)：归并排序

结语：本篇博客就到此结束了，我们的数据结构初阶的内容也完结了，大家如果想要掌握的更好的话，可以回头去刷一下数据结构初阶的题，这个我LeetCode的专栏中也一直在更新，大家可以去看一下，通过刷题来巩固知识。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。

【数据结构初阶】--文件归并排序