【数据结构初阶】--文件归并排序
🔥个人主页：@草莓熊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<stdio.h>
#include<time.h>
#include<stdlib.h>// 创建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);
}// 返回实际读到的数据个数，没有数据了，返回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[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和file2remove(file1);remove(file2);// 重命名mfile为file1rename(mfile, file1);// 当再去读取数据，一个都读不到，说明已经没有数据了// 已经归并完成，归并结果在file1int n = 0;if ((n = ReadNDataSortToFile(fout, m, file2)) == 0)break;/*if (n < 100){int x = 0;}*/}return 0;
}--大家感兴趣的话可以把代码拿着自己去测试一下，建议从少数据开始观察，这样更明显一点
往期回顾：
【数据结构初阶】--排序(一)：直接插入排序，希尔排序
【数据结构初阶】--排序(二)--直接选择排序，堆排序
【数据结构初阶】--排序(三)：冒泡排序，快速排序
【数据结构初阶】--排序(四)：归并排序
结语：本篇博客就到此结束了，我们的数据结构初阶的内容也完结了，大家如果想要掌握的更好的话，可以回头去刷一下数据结构初阶的题，这个我LeetCode的专栏中也一直在更新，大家可以去看一下，通过刷题来巩固知识。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。