往期《数据结构初阶》回顾：
【时间复杂度 + 空间复杂度】
【顺序表 + 单链表 + 双向链表】
【顺序表/链表 精选15道OJ练习】
【顺序栈 + 链式队列 + 循环队列】
【链式二叉树】
【堆 + 堆排序 + TOP-K】
【二叉树 精选9道OJ练习】
【八大排序——群英荟萃】
【八大排序——巅峰决战】
【番外篇：快速排序的前世今生】

前言：

(づ｡◕‿‿◕｡)づ hi~ 小伙伴们久等啦！(◕‿◕✿) 博主今天终于发布 【番外篇：多路归并的外排史诗】 啦！✨
特此声明：博主并没有 “跑路” 哦～～(￣▽￣*)ゞ 这篇博客其实早就写完了，只是特意等到端午节这个特别的日子发送～🎉
🎉今天不仅是端午节🐲，也是我们《数据结构初阶》系列正式完结的日子！🥳
从博主发布的第一篇《数据结构初阶》博客【时间复杂度 + 空间复杂度】到今天，不知不觉已经过去将近一个半月啦，时间过得好快！😭

这篇博客虽然篇幅不长（约 4k 字），但内容完整覆盖了理论→实践全流程～📖
博主相信，通过阅读本文，你一定能熟练掌握 大文件外部排序 —— 二路归并排序 的核心原理与实现！٩(◕‿◕｡)۶

---------------介绍---------------

一、实际情景

当待排序的数据量远远超过计算机内存容量时，直接使用常规的内部排序算法（例如：快速排序、归并排序等，之前我们学习的八大排序都是内部排序）会面临数据无法完整加载到内存的困境。

当数据无法一次性加载到内存中处理时，需要借助外部存储设备（如：硬盘、U 盘等），通过 内存与外存之间的多次数据交换 完成排序。

所以：我们就需要借助 外部排序 算法，通过协调内存与外部存储设备之间的数据交互，分阶段完成排序任务。

二、外部排序

什么是外部排序？

外部排序（External Sorting）：是一种处理 数据量远超计算机内存容量 的排序技术。

外部排序的核心思想：

• 将大规模数据拆分为多个可处理的小数据块，先在内存中对每个数据块进行排序生成有序归并段
• 再通过多路归并等策略将这些有序段逐步合并，最终得到完整的有序数据集

这种方式有效突破了内存容量的限制，成为处理海量数据排序的关键技术手段。

---

一句话总结：外部排序是内存不足时的「排序救星」：

它通过「分割数据→内存排序→归并合并」的流程，解决了传统排序无法处理海量数据的问题，本质是一种「利用外存扩展内存能力」的工程化解决方案。

---

所以：下面我们就来了解一下外部排序的经典方法：多路归并排序

三、多路归并排序

什么是多路归并排序？

多路归并排序（Multi-way Merge Sort）：是外部排序中常用的核心技术，用于解决「数据量远超内存容量」时的排序问题。

• 它的本质是 将多个有序子序列（归并段）逐步合并成一个完整的有序序列
• 它是传统二路归并排序的扩展，可同时合并K个有序序列，显著减少归并轮次

---

多路归并排序核心原理与流程：

外部排序通常分为两个阶段：预处理阶段（生成归并段） 和 归并阶段（合并有序段）

1. 预处理阶段：生成初始归并段

• 步骤：
  • 将大文件分割成若干 小数据块，每个块大小不超过内存容量
  • 依次将每个块读入内存，用 内部排序算法（如：快速排序）排序，生成 有序的归并段（临时文件）
• 示例：
  • 若内存可容纳 100MB 数据，原始文件 1GB，则分成 10 个 100MB 的块
  • 分别排序后得到 10 个有序归并段

2. 归并阶段：合并归并段

• 核心思想：利用 多路归并算法（如：k 路归并），每次从 k 个归并段中读取最小数据，合并成最终有序文件。
• 关键点：
  • 减少磁盘 I/O 次数：通过增加归并路数 k（受内存限制），减少归并轮次。
  • 缓冲区管理：在内存中为每个归并段分配输入缓冲区，以及输出缓冲区，减少读写次数。

---------------实现---------------

四、文件归并

文件二路归并排序思路是什么？

文件数据排序与归并流程：

1. 初始分块排序：

• 从原始数据中每次读取 n 个值，排序后分别写入两个临时文件 file1 和 file2

  • 例如：首次读取前 n 个值排序后写入 file1，再读取接下来的 n 个值排序后写入 file2

---

2. 首次归并操作

• 使用归并排序的思想，同时读取 file1 和 file2 中的数据，逐段比较两者的当前最小值
• 将较小的值依次尾插到一个新文件 mfile 中，最终将 mfile 合并为一个有序文件

3. 文件清理与重命名

• 删除已归并完成的 file1 和 file2
• 将 mfile 重命名为 file1，作为下一轮归并的基础有序文件

4. 后续分块与归并循环

• 再次从原始数据中读取 n 个值，排序后写入新的 file2（若原始数据已读完，则跳过此步）
• 重复步骤 2 的归并过程：
  • 将 file1（前一轮的有序结果）与 file2（新排序的块）合并到 mfile
  • 再删除旧文件并将 mfile 重命名为 file1

---

5. 终止条件与结果

• 持续上述循环，直到原始数据无法再读出 n 个值
• 最终：所有数据经多次归并后形成的完整有序数据将存储在 file1 中

文件二路归并排序怎么实现？

头文件：ExternalSort.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
//任务1：包含要使用的头文件
#include <stdio.h>
#include <stdlib.h>
#include <time.h>//任务2：声明实现文件归并的外排序需要使用“辅助函数”
//1.文件数据生成
//2.比较函数：用于调用qsort函数
void CreateNData();
int complete(const void* a, const void* b);//任务3：声明实现文件归并的外排序需要使用“核心函数”//1.从原文件中读取n个数据，将其排序后写入到新文件中
//2.合并两个已排序的文件到一个新的文件int ReadNDataSortToFile(FILE* fout, int n, const char* file1);
void MergeFile(const char* file1, const char* file2, const char* mfile);

实现文件：ExternalSort.c

#include "ExternalSort.h"/*------------------------------------------实现：“辅助的函数”------------------------------------------*/
//1.实现：“创建大量的文件数据”
void CreateNData()
{/*-----------------第一阶段：准备随机条件-----------------*///1.设置要生成随机数的数量const int N = 10000000; //生成1千万个随机整数//2.初始化随机数的种子 ----> 确保每次运行生成的随机数序列都是不同的srand((unsigned int)time(NULL));/*-----------------第二阶段：准备写入的文件-----------------*///1.定义写入的文件的文件的名称const char* file = "data.txt";//2.以“写入的模式”打开文件 （注：如果文件已经存在则将原文件清空，否则创建新的文件）FILE* fin = fopen(file, "w");//3.检查文件是否打开成功if (fin == NULL){perror("fopen fail");return;}/*-----------------第三阶段：生成随机数并将其写入到文件中-----------------*///1.使用for循环进行N次：“随机数的生成 + 写入到文件中”for (int i = 0; i < N; i++){//1.1：生成随机数int x = rand() + i;//1.2：将随机数写入文件中fprintf(fin, "%d\n", x);  //注：这里写入的时候将换行符也写入到了文件中 ---> 方便我们使用fscanf进行从文件中读取数字}//2.关闭文件fclose(fin);}/*** @brief 比较函数，用于qsort等排序算法的元素比较** @param a 指向第一个待比较元素的指针(void*通用指针类型)* @param b 指向第二个待比较元素的指针(void*通用指针类型)* @return int 返回比较结果：*             - 负数：a < b*             - 零：a == b*             - 正数：a > b** @note 1. 这是标准的qsort比较函数格式*       2. 使用指针解引用和类型转换来获取整数值*       3. 返回a-b实现升序排序，b-a可实现降序排序*       4. 注意整数溢出风险(对大数建议使用条件判断替代减法)*/
//2.实现：“两个数字的大小比较”的辅助函数 ---> 由于qsort函数的调用
int complete(const void* a, const void* b)
{// 1. 将void*指针转换为int*指针//    - 这是必要的，因为qsort使用通用指针void*//    - 我们知道实际比较的是int类型数据const int* pa = (const void*)a;const int* pb = (const void*)b;//2.解引用指针获取实际整数值int valA = *pa;int valB = *pb;// 3. 计算并返回比较结果//    - 返回valA-valB实现升序排序//    - 这种实现简洁但可能有整数溢出风险//    - 替代方案(避免溢出)://      if(valA < valB) return -1;//      if(valA > valB) return 1;//      return 0;return (valA - valB);/*上面的三步骤可以合并为一步骤：return(*(const int*)a - *(const int*)b);  //升序排序*/
}/*------------------------------------------实现：“核心的函数”------------------------------------------*//*** @brief 从输入文件中读取最多n个整数数据，排序后写入输出文件** @param fout 输入文件指针(已打开的可读文件)* @param n 请求读取的最大数据个数* @param file1 输出文件名(排序后的数据将写入此文件)* @return int 实际读取并处理的数据个数，0表示无数据或出错** @note 函数执行流程：*       1. 分配内存缓冲区*       2. 从文件读取数据*       3. 对数据进行排序*       4. 将排序结果写入新文件*       5. 清理资源并返回结果*///1.实现：“从原文件中读取n个数据，将其排序后写入到新文件中”
int ReadNDataSortToFile(FILE* fout, int n, const char* file)
{/*-------------------------------第一阶段：在内存中开辟空间又来存储从文件读到的部分数据-------------------------------*///1.在内存中开辟数组空间用于存储从文件中读取的n个数据 （空间的大小：足够存储请求的最大的空间）int* a = (int*)malloc(n * sizeof(int));if (a == NULL){perror("malloc fail");return 0;}/*-------------------------------第二阶段：从文件中读取数据到内存的数组中-------------------------------*///1.定义一个临时的变量用于存储从文件中读取的每一个数字int x;//2.定义一个变量用于：记录从文件读取到内存中的数据的数量int num = 0;//3.使用for循环从文件中读取数据for (int i = 0; i < n; i++){//3.1：判断是否读到了文件的末尾if (fscanf(fout, "%d", &x) == EOF)   //EOF表示文件结束或读取错误{ break;}//3.2：将读取的数据存储到内存的数组中a[num++] = x;}//4.检查是否读取到任何的数据if (num == 0){free(a);return 0;}/*-------------------------------第三阶段：对读取到内存中的数据进行排序-------------------------------*///使用标准库的qsort函数qsort(a, num, sizeof(int), complete);  //参数：数组指针，元素个数，元素大小，比较函数/*-------------------------------第四阶段：将排序好的数据写入到新文件中-------------------------------*///1.以“只写的模式”打开新文件file目的是为了写入排序好的数据FILE* fin = fopen(file, "w");if (fin == NULL){//1.1：文件打开失败，先释放内存free(a);//1.2：输出错误信息perror("fopen fail");//1.3：返回0表示失败return 0;}//2.使用for循环将排序好的数据写入到新文件file中for (int i = 0; i < num; i++){fprintf(fin, "%d\n", a[i]);}/*-------------------------------第五阶段：释放资源-------------------------------*///1.释放动态开辟的内存free(a);//2.关闭新文件filefclose(fin);/*-------------------------------第六阶段：返回实际处理的数据个数-------------------------------*/return num;
}/*** @brief 合并两个已排序的整数文件到一个新文件（归并操作）** @param file1 第一个已排序的输入文件名* @param file2 第二个已排序的输入文件名* @param mfile 合并后的输出文件名** @note 该函数执行经典的两路归并操作，要求：*       1. 输入文件必须已按升序排列*       2. 文件内容为每行一个整数*       3. 输出文件将包含所有输入数据并保持有序*/
//2.实现：“合并两个已排序文件到一个新文件中”
void MergeFile(const char* file1, const char* file2, const char* mfile)
{/*-------------------------------第一阶段：打开文件-------------------------------*///1.以“只读模式”打开文件file1FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen fail for file1");  //更明确的错误信息return;}//2.以“只读模式”打开文件file2FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen fail for file2");fclose(fout1);  //资源清理：关闭已经成功打开的第一个文件return;}//3.以“只写模式”打开文件mfileFILE* fin = fopen(mfile, "w");if (fin == NULL){perror("fopen fail for mfile");fclose(file1);fclose(file2);return;}/*-------------------------------第二阶段：文件归并-------------------------------*///1.定义两个变量存储从两个小文件中读取的数据int x1, x2;//2.定义两个变量存储fscanf函数的返回值 --> 目的：判断何时停止归并int ret1, ret2;//3.先分别从两个小文件中读取一个数据到变量中ret1 = fscanf(fout1, "%d", &x1);ret2 = fscanf(fout2, "%d", &x2);//4.使用while循环进行双路归并 while (ret1 != EOF && ret2 != EOF) //当两个小文件中有一个文件已经读取结束时，归并就结束了 ---> 反面就是while循环的条件{//4.1：当从文件file1中读取的数据更小的话，则将x1添加到新文件mfile中if (x1 < x2){//1.写入fprintf(fin, "%d\n", x1);//2.再读ret1 = fscanf(fout1, "%d", &x1);}//4.2：当从文件file2中读取的数据更小的话，则将x2添加到新文件mfile中else{//1.写入fprintf(fin, "%d\n", x2);//2.再读ret2 = fscanf(fout2, "%d", &x2);}}/*-------------------------------第三阶段：处理某一个文件中的剩余数据-------------------------------*///情况1：小文件file1还有剩余数据（file2已耗尽）while (ret1 != EOF){//1.写入fprintf(fin, "%d\n", x1);//2.再读ret1 = fscanf(fout1, "%d", &x1);}//情况2：小文件file2还有剩余数据（file1已耗尽）while (ret2 != EOF){//1.写入fprintf(fin, "%d\n", x2);//2.再读ret2 = fscanf(fout2, "%d", &x2);}/*-------------------------------第三阶段：资源清理-------------------------------*/fclose(fout1);fclose(fout2);fclose(fin);
}

主程序文件：Main.c

#include "ExternalSort.h"/*** @brief 主函数 - 实现外部排序的核心流程** @return int 程序退出状态码（0表示成功）** @note 该程序实现完整的外部排序过程：*       1. 生成测试数据*       2. 分割大文件为有序小文件*       3. 多轮归并排序*       4. 最终生成完全有序的大文件*/int main()
{/*-------------------------------第一阶段：数据准备-------------------------------*///1.生成包含随机数的初始随机文件"data.txt"//CreateNData();//2.定义临时文件名const char* file1 = "file1.txt";  //主归并文件（每轮归并后保存中间结果）const char* file2 = "file2.txt";  //辅助归并文件（存储新读取的数据块）const char* mfile = "mfile.txt";  //归并临时文件（存储每轮归并结果）/*-------------------------------第二阶段：文件初始化-------------------------------*///1.以“只读模式”打开原始数据文件"data.txt"FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen fail");return 1; //返回非零表示错误退出}/*-------------------------------第三阶段：原始数据文件分割-------------------------------*///1.设置分割出的每个小文件的大小（根据内存容量调整）int M = 1000000;  //每次处理1百万个整数//2.读取并排序第一批数组到file1中ReadNDataSortToFile(fout, M, file1);//3.读取并排序第一批数组到file2中ReadNDataSortToFile(fout, M, file2);/*-------------------------------第四阶段：多轮归并-------------------------------*///1.使用while死循环进行多轮归并while (1) //我们并不清楚大文件中到底有多少的数据，即我们不清楚我们要归并多少轮 ---->  所以：无限循环，通过内部break退出{/*----------第一步：归并存储在两个小文件file1和file2中的已经排好序的数据到一个较大的文件mfile中----------*/MergeFile(file1, file2, mfile);/*----------第二步：清理两个小文件file1和file2----------*/if (remove(file1) != 0) //安全删除不再需要的中间文件perror("Warning: Failed to remove file1");if (remove(file2) != 0)perror("Warning: Failed to remove file2");/*----------第三步：将归并出来的那个较大的文件mfile重命名为file1----------*/if (rename(mfile, file1) != 0) //安全重命名文件mfile {perror("Warning: Failed to rename mfile");break;}/*----------第四步：从原数据文件中读取下一批数据到文件file2----------*///1.记int read_count = 0;//2.读read_count = ReadNDataSortToFile(fout, M, file2);//3.检if (read_count == 0){break; // 读取不到数据，排序完成}/*1.归并2.清理3.轮转4.再读*/// 调试用代码块（可取消注释）if (read_count < M){printf("最后一块有 %d 个元素\n", read_count);;}}/*-------------------------------第五阶段：释放资源 + 结束程序-------------------------------*///1.关闭原始数据文件fclose(fout);//2.程序成功结束return 0;
}

运行结果