深入浅出多路归并：原理、实现与实战案例解析

文章目录

二路归并
多路归并
- 方法一：指针遍历（多指针比较法）
- 方法二：小根堆法（最小堆归并）
实际场景
- 外部排序
经典题目
- 丑数Ⅱ
- - 方法一：三指针法
  - 方法二：优先队列法（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();
}