往期《數據結構初階》回顧：
【時間復雜度 + 空間復雜度】
【順序表 + 單鏈表 + 雙向鏈表】
【順序表/鏈表 精選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;
}

運行結果