【不看会后悔系列】排序之——文件归并【史上最全详解】~

---

前言

学习了归并排序了之后，我们来了解一下文件是怎么归并的。、

要看归并排序请戳我~

---

一、何为文件归并？

文件归并外排序（External Sorting with Merge）是一种专门处理大规模数据的排序算法，适用于数据量大到无法一次全部加载到内存的情况。主要用于处理硬盘等外部存储设备上的数据，而不是内存中的数据。

外排序的核心思想：

1. 排序阶段（分割数据）：由于数据量过大，无法一次性全部放入内存，所以将数据分块处理。每次读取内存能够容纳的一部分数据，对这部分数据进行排序，然后将排序后的数据存储到临时文件中。重复这个过程，直到所有数据都被处理并生成多个有序的临时文件。

2. 归并阶段（合并文件）：将之前生成的多个有序临时文件按一定方式归并成一个大的有序文件。归并排序的特点是不需要随机访问数据，只需按顺序读入数据进行归并，因此特别适合外排序。

步骤总结：

• Step 1: 分割数据并对每个分块排序（生成多个有序的临时文件）。
• Step 2: 将这些有序的临时文件逐步归并，直到所有数据整合成一个完整的有序文件。

外排序与内排序的区别：

• 外排序：处理无法完全加载到内存中的数据，使用“排序-归并”策略，依赖外部存储设备。
• 内排序：处理能完全加载到内存中的数据，常用排序算法如快速排序、堆排序等都属于内排序。

归并排序作为一种适用于顺序读取数据的算法，可以同时用于内存中的排序和外存储的排序，因此在外排序中也广泛应用。

---

二、文件归并思路分析

假设这是我们未排序的文件

1. 分块排序：

   • 读取内存能容纳的 n 个数据，进行排序。
   • 将排序后的数据写入到 file1。
   • 再次读取 n 个数据，排序后写入到 file2。

   

2. 初步归并：

   • 通过归并排序的思想，同时从 file1 和 file2 中按顺序读取数据。
   • 比较 file1 和 file2 的当前值，将较小的值依次写入到 mfile 中。
   • 继续此过程，直到 file1 和 file2 的数据全部归并到 mfile 中，生成一个新的有序文件。

   

3. 文件重命名和清理：

   • 删除 file1 和 file2，释放存储空间。
   • 将 mfile 重命名为 file1，以便后续继续归并。

   

4. 继续处理新的数据：

   • 继续读取 n 个新的数据进行排序，并将其写入到 file2。
   • 再次执行归并操作，将 file1 和 file2 归并成一个新的有序文件，存入 mfile。

   

5. 重复归并，直到结束：

   • 重复步骤 2 和步骤 4，直到所有数据处理完毕。
   • 最终归并后的有序文件存放在 file1 中，完成整个排序过程。

   

文件归并的特点：

• 每次只需在内存中处理一小部分数据，避免内存溢出问题。
• 使用归并排序保证了数据在外存储中按顺序处理，高效完成排序。

---

三、创造多数据文件

思路如下：

1. 定义随机数个数 n:

   int n = 1000000;
   

   • 定义 n 为 1000000，表示需要在文件中生成 100 万个随机数。

2. 初始化随机数种子:

   srand(time(0));
   

   • 使用 srand(time(0)) 来初始化随机数种子，确保每次运行时生成的随机数序列不同。

3. 定义文件名:

   const char* file = "data.txt";
   const char* file1 = "file1";
   const char* file2 = "file2";
   

   • 定义了三个文件路径，data.txt 用于存储生成的随机数，file1 和 file2 用于后续归并排序中的临时文件。

4. 打开文件 data.txt（用于写入数据）:

   FILE* fin = fopen(file, "w");
   if (fin == NULL)
   {perror("fopen error");return;
   }
   

   • 使用 fopen 以写入模式 (w) 打开 data.txt，若打开失败，则输出错误信息并退出函数。

5. 生成并写入随机数:

   for (int i = 0; i < n; i++)
   {int x = rand() + i;fprintf(fin, "%d\n", x);
   }
   

   • 使用 for 循环生成 n 个随机数，并通过 fprintf 将它们逐行写入到 data.txt 文件中。
   • rand() 用于生成随机数，并在每个随机数上加上当前循环索引 i，以增加随机数的分布多样性。

6. 关闭文件 data.txt:

   fclose(fin);
   

   • 随机数写入完成后，关闭 data.txt 文件。

7. 清空 file1 和 file2:

   FILE* f1 = fopen(file1, "w");
   FILE* f2 = fopen(file2, "w");
   if (f1 == NULL || f2 == NULL)
   {perror("fopen file1 or file2 fail!");return;
   }
   

   • 分别以写模式打开 file1 和 file2 文件。如果文件不存在，则会创建；如果文件存在，则清空内容。

8. 关闭 file1 和 file2:

   fclose(f1);
   fclose(f2);
   

   • 清空完成后，关闭 file1 和 file2，准备后续排序时使用。

总结：

• 这个函数的核心任务是生成一个包含随机数的文件 data.txt，并准备两个空的文件 file1 和 file2，为接下来的外部归并排序操作做准备。
• 通过这种方式，数据先被分批处理、排序并写入 file1 和 file2，最后通过归并的方式组合成有序文件。

像这样就创建成功了

代码如下：

// 创建有 N 个数据的文件，并同时创建 file1 和 file2
void CreatNData()
{// 随机数造数据int n = 1000000;srand(time(0));const char* file = "data.txt";const char* file1 = "file1";const char* file2 = "file2";// 打开文件(写数据)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);// 清空 file1 和 file2，以便后续使用FILE* f1 = fopen(file1, "w");FILE* f2 = fopen(file2, "w");if (f1 == NULL || f2 == NULL){perror("fopen file1 or file2 fail!");return;}// 关闭 file1 和 file2fclose(f1);fclose(f2);
}

---

四、前置准备——堆排序

后面拿n个数据读取到file1和file2中的时候需要排序，我们这里使用堆排序

J桑前面讲过好多次堆排序，这里就直接给代码啦~

需要看堆排序戳我~~~

//先把堆排拿过来备用
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩⼦中⼤的那⼀个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}

---

五、两个文件写入到第三个文件

这段代码通过归并排序的思想，将 file1 和 file2 中的数据按序合并到 mfile 中。具体流程如下：

1. 打开文件：以读取模式打开 file1 和 file2，以写入模式打开 mfile。
2. 归并数据：通过循环从 file1 和 file2 读取数据，比较大小后将较小的值写入 mfile。
3. 处理剩余数据：当一个文件的数据读完后，将另一个文件剩下的数据依次写入 mfile。
4. 关闭文件：处理完成后，关闭所有文件。

这里简单解释一下 fscanf 的用法


fscanf发生错误时会返回EOF，因此我们可以用EOF来判断

代码如下：

// file1⽂件的数据和file2⽂件的数据归并到mfile⽂件中
void MergeFile(const char* file1, const char* file2, const char* mfile)
{//创立三个文件，以读的方式打开file1和file2，以写的方式打开mfileFILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen file1 fail!");exit(-1);}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen file2 fail!");exit(-1);}FILE* fin = fopen(mfile, "w");if (fin == NULL){perror("fopen mfile fail!");exit(-1);}// 这⾥跟内存中数组归并的思想完全类似，只是数据在硬盘⽂件中⽽已// 依次读取file1和file2的数据，谁的数据⼩，谁就往mfile⽂件中去写// file1和file2其中⼀个⽂件结束后，再把另⼀个⽂件未结束⽂件数据，// 依次写到mfile的后⾯int num1, num2;int ret1 = fscanf(fout1, "%d\n", &num1);int ret2 = fscanf(fout2, "%d\n", &num2);while (ret1 != EOF && ret2 != EOF){if (num1 < num2){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}else{fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}}while (ret1 != EOF){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}while (ret2 != EOF){fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}///打开文件后记得关闭fclose(fout1);fclose(fout2);fclose(fin);
}

---

六、读 N 个数据返回给文件,并返回读到数据的个数

这段代码的功能是从文件中读取 n 个数据，排序后再写入另一个文件，并返回实际读取到的数据个数。具体流程如下：

1. 读取数据：

   • 使用 fscanf 从文件 fout 中读取整数，最多读取 n 个数据，存储在数组 a 中。
   • 通过 i 记录实际读取到的数据个数，循环读取直到达到 n 或文件结束。

2. 检查数据数量：

   • 如果没有读取到任何数据，直接返回 0，表示读取失败或文件为空。

3. 堆排序：

   • 如果读取到了数据，调用 HeapSort 对数组 a 中的 i 个数据进行排序。

4. 写入排序后的数据：

   • 打开目标文件 file，并将排序后的数据逐行写入。
   • 文件写入完成后关闭文件。

5. 返回值：

   • 返回实际读取并排序的数据个数 i，用于后续处理。

关键点：

• 数据读取使用 fscanf，按行读取整数。我们构建父本的时候也是按行%d\n形式的
• 使用堆排序 HeapSort 对数据进行排序。
• 数据排序后写回到指定的 file 文件中。

代码如下：

// 返回读取到的数据个数,并排序,读 N 个数据返回给文件,并返回读到数据的个数
int ReadNNumSortToFile(FILE* fout, int* a, int n, const char* file)
{//数据读到 x 中int x = 0;// i 表示读到数据的个数int i = 0;while (i < n && fscanf(fout, "%d\n", &x) != EOF){a[i++] = x;}//如果一个数据都没读到，不用排序了，返回0if (i == 0){return i;}//读到的数据堆排序HeapSort(a, i);//把排序过的数组放回文件中去FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen file fail!");exit(-1);}for (int j = 0; j < i; j++){fprintf(fin, "%d\n", a[j]);}//记得关闭文件fclose(fin);return i;
}

---

七、文件归并

该函数的目的是通过外部归并排序，将大文件 file 按照块处理，逐块排序并归并，最终生成一个有序文件。

开始之前，我们先来了解两个函数：
remove：

rename:

用这两个函数就可以有效删除和重命名我们的文件，合理运用返回值增强代码健壮性，还可以当作判断条件

1. 文件打开：

   FILE* fout = fopen(file, "r");
   

   • 以只读模式打开要排序的文件 file，如果打开失败，程序退出。

2. 定义临时文件：

   const char* file1 = "file1";
   const char* file2 = "file2";
   const char* mfile = "mfile";
   

   • file1 和 file2 用于存储分块后的数据，mfile 是临时文件，存储归并后的数据。

3. 内存分配：

   int* a = (int*)malloc(sizeof(int) * n);
   

   • 为数组 a 分配大小为 n 的内存空间，用于存储从文件中读取的数据。n 是每次读取数据的大小，取决于内存可用空间。

4. 数据分块并排序：

   int readCount1 = ReadNNumSortToFile(fout, a, n, file1);
   int readCount2 = ReadNNumSortToFile(fout, a, n, file2);
   

   • 调用 ReadNNumSortToFile 函数，从 file 中读取 n 个数据，排序后分别写入 file1 和 file2。
   • 读取的结果存储在 readCount1 和 readCount2，如果两个文件都没有数据，直接退出函数。

5. 循环归并：

   while (1)
   

   • 进入循环，将 file1 和 file2 中的数据归并到 mfile 中。

6. 文件处理：

   • 归并：

     MergeFile(file1, file2, mfile);
     

     • 调用 MergeFile 函数，将 file1 和 file2 的内容按顺序归并到 mfile。

   • 删除与重命名：

     remove(file1);
     remove(file2);
     rename(mfile, file1);
     

     • 删除 file1 和 file2，然后将 mfile 重命名为 file1，为下一次归并做准备。

7. 继续读取数据并归并：

   if (ReadNNumSortToFile(fout, a, n, file2) == 0)
   {break;
   }
   

   • 再次读取 n 个数据排序并存储到 file2，如果无法再读取数据，说明归并结束，退出循环。

8. 结束处理：

   fclose(fout);
   free(a);
   

   • 关闭文件并释放内存。

核心思想：

• 通过逐块读取数据到内存进行排序，随后将多个排序好的块文件进行归并，最终得到一个有序的文件。每次归并后的文件会循环处理，直至所有数据排序完成。

也就是我们一开始画的这张图，是我们整个文件归并的大框架

代码实现：

// MergeSortFile的第⼆个是每次取多少个数据到内存中排序，然后写到⼀个⼩⽂件进⾏归并
// 这个n给多少取决于我们有多少合理的内存可以利⽤，相对⽽⾔n越⼤，更多数据到内存中排序后，
// 再⾛⽂件归并排序，整体程序会越快⼀些。
void MergeSortFile(const char* file, int n)
{// 以写的方式打开文件 fileFILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen file fail!");exit(-1);}// 定义三个文件 file1, file2, mfileconst char* file1 = "file1";const char* file2 = "file2";const char* mfile = "mfile";// 分割成⼀段⼀段数据，内存排序后写到，⼩⽂件int* a = (int*)malloc(sizeof(int) * n);if (a == NULL){perror("malloc fail!");exit(-1);}int readCount1 = ReadNNumSortToFile(fout, a, n, file1);int readCount2 = ReadNNumSortToFile(fout, a, n, file2);if (readCount1 == 0 && readCount2 == 0) {fclose(fout);free(a);return; // 如果两个文件都没有数据，直接返回}//循环归并获取元素while (1){// file1和file2⽂件归并到mfile⽂件中MergeFile(file1, file2, mfile);//删除file1和file2if (remove(file1) != 0 || remove(file2) != 0){perror("Error deleting file");exit(-1);}//重命名mfile为file1if (rename(mfile, file1) != 0){perror("Error renaming file");exit(-1);}// 读取N个数据到file2，继续⾛归并// 如果⼀个数据都没读到，则归并结束了if (ReadNNumSortToFile(fout, a, n, file2) == 0){break;}}printf("%s 文件成功排序到%s\n", file, file1);// 别忘了关闭文件，释放a空间fclose(fout);free(a);
}

---

八、文件归并完整代码总结

1. 运行代码

到这里我们所有的框架都搭建完了，现在要做的就是将他们结合起来

完整代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>// 创建有 N 个数据的文件，并同时创建 file1 和 file2
void CreatNData()
{// 随机数造数据int n = 1000000;srand(time(0));const char* file = "data.txt";const char* file1 = "file1";const char* file2 = "file2";// 打开文件(写数据)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);// 清空 file1 和 file2，以便后续使用FILE* f1 = fopen(file1, "w");FILE* f2 = fopen(file2, "w");if (f1 == NULL || f2 == NULL){perror("fopen file1 or file2 fail!");return;}// 关闭 file1 和 file2fclose(f1);fclose(f2);
}//先把堆排拿过来备用
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩⼦中⼤的那⼀个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}// file1⽂件的数据和file2⽂件的数据归并到mfile⽂件中
void MergeFile(const char* file1, const char* file2, const char* mfile)
{//创立三个文件，以读的方式打开file1和file2，以写的方式打开mfileFILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen file1 fail!");exit(-1);}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen file2 fail!");exit(-1);}FILE* fin = fopen(mfile, "w");if (fin == NULL){perror("fopen mfile fail!");exit(-1);}// 这⾥跟内存中数组归并的思想完全类似，只是数据在硬盘⽂件中⽽已// 依次读取file1和file2的数据，谁的数据⼩，谁就往mfile⽂件中去写// file1和file2其中⼀个⽂件结束后，再把另⼀个⽂件未结束⽂件数据，// 依次写到mfile的后⾯int num1, num2;int ret1 = fscanf(fout1, "%d\n", &num1);int ret2 = fscanf(fout2, "%d\n", &num2);while (ret1 != EOF && ret2 != EOF){if (num1 < num2){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}else{fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}}while (ret1 != EOF){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}while (ret2 != EOF){fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}///打开文件后记得关闭fclose(fout1);fclose(fout2);fclose(fin);
}// 返回读取到的数据个数,并排序,读 N 个数据返回给文件,并返回读到数据的个数
int ReadNNumSortToFile(FILE* fout, int* a, int n, const char* file)
{//数据读到 x 中int x = 0;// i 表示读到数据的个数int i = 0;while (i < n && fscanf(fout, "%d\n", &x) != EOF){a[i++] = x;}//如果一个数据都没读到，不用排序了，返回0if (i == 0){return i;}//读到的数据堆排序HeapSort(a, i);//把排序过的数组放回文件中去FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen file fail!");exit(-1);}for (int j = 0; j < i; j++){fprintf(fin, "%d\n", a[j]);}//记得关闭文件fclose(fin);return i;
}// MergeSortFile的第⼆个是每次取多少个数据到内存中排序，然后写到⼀个⼩⽂件进⾏归并
// 这个n给多少取决于我们有多少合理的内存可以利⽤，相对⽽⾔n越⼤，更多数据到内存中排序后，
// 再⾛⽂件归并排序，整体程序会越快⼀些。
void MergeSortFile(const char* file, int n)
{// 以写的方式打开文件 fileFILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen file fail!");exit(-1);}// 定义三个文件 file1, file2, mfileconst char* file1 = "file1";const char* file2 = "file2";const char* mfile = "mfile";// 分割成⼀段⼀段数据，内存排序后写到，⼩⽂件int* a = (int*)malloc(sizeof(int) * n);if (a == NULL){perror("malloc fail!");exit(-1);}int readCount1 = ReadNNumSortToFile(fout, a, n, file1);int readCount2 = ReadNNumSortToFile(fout, a, n, file2);if (readCount1 == 0 && readCount2 == 0) {fclose(fout);free(a);return; // 如果两个文件都没有数据，直接返回}//循环归并获取元素while (1){// file1和file2⽂件归并到mfile⽂件中MergeFile(file1, file2, mfile);//删除file1和file2if (remove(file1) != 0 || remove(file2) != 0){perror("Error deleting file");exit(-1);}//重命名mfile为file1if (rename(mfile, file1) != 0){perror("Error renaming file");exit(-1);}// 读取N个数据到file2，继续⾛归并// 如果⼀个数据都没读到，则归并结束了if (ReadNNumSortToFile(fout, a, n, file2) == 0){break;}}printf("%s 文件成功排序到%s\n", file, file1);// 别忘了关闭文件，释放a空间fclose(fout);free(a);
}int main()
{//CreatNData();// 一次排100000个数据MergeSortFile("data.txt", 100000);return 0;
}

---

2. 运行截图

我们来运行一下吧~

先创建数据

来到我们文件中，可以看到我们初始数据，还有file1,fiel2都创建好了。

再来运行排序

打开我们的文件，可以看到在file1中数据排好了升序，代表文件归并成功~

数据太多了，J桑就不都给大家看啦~

---

总结

到这里，我们文件归并的内容就结束啦~

最重要的是要先搭建出文件归并的框架，像这样大事化小的思路，然后先把框架化为代码，再去补充其他需要用到的函数~

那么，就谢谢大家啦~