深入淺出多路歸并：原理、實現與實戰案例解析

文章目錄

二路歸并
多路歸并
- 方法一：指針遍歷（多指針比較法）
- 方法二：小根堆法（最小堆歸并）
實際場景
- 外部排序
經典題目
- 丑數Ⅱ
- - 方法一：三指針法
  - 方法二：優先隊列法（K路歸并）
  - 方法三：優先隊列法（BFS）（非多路歸并）
- 其他題目
總結

歸并，在計算機科學中，一般是以歸并排序出現的，就是將兩個或者多個有序的序列合并成一個序列。

二路歸并

舉個二路歸并的例子：

輸入兩個有序數組：
[1, 4, 7]
[2, 5, 6, 8]歸并后得到：
[1, 2, 4, 5, 6, 7, 8]

二路歸并實現上很簡單，我們很容易就能想到用兩個指針，分別指向兩個數組的起始位置，然后不斷地兩兩比較指針所指地數值，將小的放到新數組中去，最終遍歷完兩個數組就行了。

多路歸并

但是多路歸并涉及到了多個有序的數組，我們要將這多個有序數組合并成一個。多路歸并一共有兩個方法。

方法一：指針遍歷（多指針比較法）

每個數組維護一個指針，指向當前元素。每次在這 k 個數組當前指向的元素中找到最小值，將其加入結果數組，并將該元素所屬數組的指針后移。這個過程重復進行，直到所有數組遍歷完畢。

每次選擇最小值需要遍歷所有指針，時間復雜度為 O(k)；
如果總共有 n 個元素需要合并，時間復雜度為 O(n × k)。

方法二：小根堆法（最小堆歸并）

我們使用一個最小堆（優先隊列）來優化每次找最小值的操作：

首先將每個數組的第一個元素（及其數組索引、元素索引）加入小根堆；
每次彈出堆頂元素（即當前最小值），將其加入結果數組；
如果該元素所屬數組還有剩余元素，則將下一個元素加入堆；
重復直到堆為空。

由于堆的大小最多為 k，每次插入和刪除的時間復雜度是 O(log k)，總共處理 n 個元素，因此整體時間復雜度為 O(n × log k)，明顯優于指針遍歷法。

假設我們有如下三個有序數組：

text復制編輯arr1 = [1, 4, 7]
arr2 = [2, 5, 8]
arr3 = [3, 6, 9]

使用最小堆歸并過程如下：

初始堆：[1(arr1), 2(arr2), 3(arr3)] → 彈出 1，加入結果，arr1 指針后移，入堆 4；
堆變為：[2(arr2), 3(arr3), 4(arr1)] → 彈出 2，加入結果，入堆 5；
堆變為：[3(arr3), 4(arr1), 5(arr2)] → 彈出 3，加入結果，入堆 6；
…

實際場景

當我們需要對超大文件（如幾個 GB、甚至 TB 的日志、數據庫快照等）進行排序時，它們無法一次性加載進內存，常規排序算法（如快排、歸并排序）在內存中就不適用了。

于是我們采用 外部排序（External Merge Sort）。

外部排序

步驟1： 分段排序

1.先將超大文件分成多份可以加載進內存的小塊。

2.將這k個小塊每一塊都讀進內存進行快速排序，保證每一塊都是有序的。

3.將排序后的每塊都重新記錄回磁盤。

步驟2： 多路歸并

通過步驟1我們得到了k組有序的文件，現在是要把它們合并成一個有序文件。

1.k個文件各自都有一個指針指向當前最小的數據。

2.每次都讀取k個指針所指的數據進入內存。

3.比較出最小的寫入最終的輸出文件sorted_output.txt中。

4.將最小的那個文件的指針后移一位。

重復以上步驟，最終就可以得到排序好的最終輸出文件sorted_output.txt。

經典題目

丑數Ⅱ

讓我們通過一個經典的 LeetCode 問題來看多路歸并的實際應用。

問題描述: 丑數是只包含質因數 2、3、5 的正整數。給定整數 n，返回第 n 個丑數。前幾個丑數序列：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …

**問題分析:**分析題目我們得知，丑數是由2，3，5中的任意幾個乘起來得到的。每個丑數都可以由更小的丑數乘以2、3或5得到，并且不會遺漏。

這意味著我們可以構造三個"虛擬"的有序序列：

序列1：所有丑數 × 2
序列2：所有丑數 × 3
序列3：所有丑數 × 5

我們的任務就是對這三個序列進行多路歸并！

方法一：三指針法

維護一個數組 ugly[] 存儲前 n 個丑數，并使用三個指針分別追蹤當前乘以 2、3 和 5 所得到的候選值。每次從候選中選出最小值作為下一個丑數，同時相應地移動對應指針，以避免重復并保持有序。該方法總共找n次，每次需要進行k次的比較，所以最終時間復雜度為 O(n*k)，但是因為這道題目的序列個數只有3個，所以其實最終的時間復雜度只有O(n)。

public static int nthUglyNumber(int n) {int[] ugly = new int[n];ugly[0]=1;int i2=0,i3=0,i5=0;int next2=1,next3=1,next5=1;for(int i=1;i<n;i++){next2=ugly[i2]*2;next3=ugly[i3]*3;next5=ugly[i5]*5;ugly[i]=Math.min(next2,Math.min(next3,next5));if(ugly[i]==next2){i2++;}if(ugly[i]==next3){i3++;}if(ugly[i]==next5){i5++;}}return ugly[n-1];
}

方法二：優先隊列法（K路歸并）

上面的方法使用三個指針記錄每一組數當前訪問的元素，然后每次需要找最小數的時候我們進行挨個比較找出最小數。這里我們使用優先隊列來替換掉這個挨個比較找出最小值的過程，我們在優先隊列中保存著三組數當前指針所指的位置，每次都出堆，就能很快地找出最小值了。保證這個堆的大小一直都是k（k為數組個數），總共需要找n次，所以最終的時間復雜度是O(nlogk)。

public static int nthUglyNumber(int n) {int[] ugly = new int[n];ugly[0] = 1;int i2 = 0, i3 = 0, i5 = 0;PriorityQueue<Integer> pq = new PriorityQueue<>();pq.add(2);pq.add(3);pq.add(5);Set<Integer> set = new HashSet<>();set.add(2);set.add(3);set.add(5);for (int i = 1; i < n; i++) {int nextUgly = pq.poll();ugly[i] = nextUgly;if (ugly[i] == ugly[i2] * 2) {i2++;if (!set.contains(ugly[i2] * 2)) {pq.add(ugly[i2] * 2);set.add(ugly[i2] * 2);}}if (ugly[i] == ugly[i3] * 3) {i3++;if (!set.contains(ugly[i3] * 3)) {pq.add(ugly[i3] * 3);set.add(ugly[i3] * 3);}}if (ugly[i] == ugly[i5] * 5) {i5++;if (!set.contains(ugly[i5] * 5)) {pq.add(ugly[i5] * 5);set.add(ugly[i5] * 5);}}}return ugly[n - 1];}

方法三：優先隊列法（BFS）（非多路歸并）

還有一種使用優先隊列的方法來解決這道題目，一開始其實我是用這個方法解決的這道題目，我以為這是多路歸并，但是怎么想怎么不對，現在我認為這是一種廣度優先遍歷的思想。

我設置一個優先隊列，我們從 1 開始，把它看作丑數生成樹的“根節點”。接著每次取出當前最小的一個丑數 ugly，再擴展它的三個“鄰居”：ugly*2, ugly*3, ugly*5，把還沒見過的加入堆中，保證后續訪問。如此往復。直到循環了n次，找到了第n小的丑數。

圖中的 BFS	這段丑數代碼中的等價含義
從起點開始遍歷鄰居	從 `1` 開始擴展出 `12`, `13`, `1*5`
使用隊列維護訪問順序	使用最小堆 PriorityQueue 保證順序
訪問節點后標記為已訪問	使用 `Set<Long> seen` 做去重
一層一層按順序擴展	丑數是從小到大、層層構造的
不重復訪問同一節點	用 `seen` 避免重復乘積

public static int nthUglyNumber(int n) {int ulgy=1;PriorityQueue<Long> pq = new PriorityQueue<>();Set<Long> seen = new HashSet<>();pq.add(1L);seen.add(1L);for(int i=1;i<n;i++){long nextUlgy = pq.poll();if(seen.add(nextUgly*2)){pq.add(nextUgly*2);}if(seen.add(nextUgly*3)){pq.add(nextUgly*3);}if(seen.add(nextUgly*5)){pq.add(nextUgly*5);}}return pq.poll().intValue();
}