文章目录
归并，在计算机科学中，一般是以归并排序出现的，就是将两个或者多个有序的序列合并成一个序列。
二路归并
举个二路归并的例子：
输入两个有序数组：
[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 开始扩展出 1*2, 1*3, 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();
}
其他题目
总结
总结来说，多路归并是一种非常实用的思想，不仅能在传统排序问题中提升效率，更在很多“按顺序生成”类的问题中大放异彩。特别是在内存受限、数据量庞大的现实场景中，它往往是不可替代的选择。掌握它，也就掌握了不少高频题的核心解法。