在日常的算法学习和软件开发中，我们经常遇到处理有序数据结构的情况。有序数组的一个核心优势在于，我们可以利用其“有序性”来设计比暴力搜索更高效的算法。今天，我们将深入探讨一个经典且有趣的问题：如何将三个已排序的数组合并成一个新的有序数组。
这不仅仅是关于数组操作的问题，更是理解双指针技术、归并排序核心思想以及时间复杂度权衡的绝佳机会。无论你是正在准备面试，还是在优化实际的数据处理流程，这篇文章都将为你提供从基础到高效的全方位解析。
问题陈述与初步思考
首先，让我们明确一下我们要解决的具体问题。
任务：给定三个按升序排列的数组 INLINECODE0c0ca799、INLINECODE827703f0 和 INLINECODEe15e294b，我们的目标是编写一个算法，将它们合并成一个新的数组 INLINECODEdef151b3，并确保 D[] 也是按升序排列的。
示例场景：
> 输入：
> A = [1, 2, 3, 4, 5]
> B = [2, 3, 4]
> C = [4, 5, 6, 7]
>
> 输出：
> D = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]
我们来看看另一个例子，为了验证不同长度数组的合并情况：
> 输入：
> A = [1, 2, 3, 5]
> B = [6, 7, 8, 9]
> C = [10, 11, 12]
>
> 输出：
> D = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12]
朴素方法：先合并后排序
面对这个问题，最直观、最容易想到的方法（我们通常称之为“朴素方法”或“暴力法”）思路非常简单：既然我们要一个包含所有元素且有序的数组，为什么不先把它们拼在一起，然后再进行排序呢？
这种方法不需要复杂的逻辑，只需要遍历所有数组将元素放入新数组，然后调用编程语言内置的排序函数即可。
#### 算法步骤
我们可以这样设计我们的算法：
- 初始化：获取用户输入的数组 A、B 和 C 的大小（或直接使用初始化好的数组）。
- 创建容器：创建一个新的空数组（或列表）D，用于存放合并后的结果。
- 数据搬运：遍历数组 A，将其所有元素添加到 D 中；对数组 B 和 C 重复同样的操作。
- 统一排序：此时，数组 D 包含了所有的元素，但是是无序的。我们对 D 调用标准库的排序函数（如 INLINECODEc5c1982c 或 INLINECODE903c30ef）。
- 输出结果：打印或返回排序后的数组 D。
#### 复杂度分析
虽然这种方法实现起来非常快，但让我们深入分析一下它的性能。假设三个数组的长度分别为 $n$、$m$ 和 $p$。
- 时间复杂度：我们需要遍历所有元素进行复制，这需要 $O(n + m + p)$ 的时间。然而，最耗时的部分是排序。对 $K = (n+m+p)$ 个元素进行排序，通常的平均时间复杂度是 $O(K \log K)$，也就是 $O((n+m+p) \log (n+m+p))$。
- 空间复杂度：我们需要一个大小为 $n+m+p$ 的数组 D 来存储数据，因此空间复杂度是 $O(n+m+p)$。
为什么这种方法不是最优的？
因为它完全忽略了输入数组已经是有序的这一重要信息。这意味着我们在做重复工作。如果利用现有的顺序，我们可以做得更好。但在某些情况下（例如数组长度非常小，或者开发时间极其紧迫），这种简单粗暴的方法依然具有其实用价值。
#### 代码实现
让我们用几种主流的编程语言来实现这个朴素方案，看看代码是如何组织的。
C++ 实现
// C++ 代码实现：朴素合并后排序法
#include
using namespace std;
// 函数功能：将三个有序数组合并并排序
vector mergeThreeSortedArrays(vector& A, vector& B, vector& C) {
vector D;
// 步骤 1: 将数组 A 的所有元素插入到 D 中
for (int i = 0; i < A.size(); i++) {
D.push_back(A[i]);
}
// 步骤 2: 将数组 B 的所有元素插入到 D 中
for (int i = 0; i < B.size(); i++) {
D.push_back(B[i]);
}
// 步骤 3: 将数组 C 的所有元素插入到 D 中
for (int i = 0; i < C.size(); i++) {
D.push_back(C[i]);
}
// 步骤 4: 对合并后的数组 D 进行升序排序
// std::sort 的底层实现通常是 Introsort（混合快速排序、堆排序和插入排序）
sort(D.begin(), D.end());
return D;
}
// 主函数：测试我们的逻辑
int main() {
// 测试用例
vector A = { 1, 2, 3, 5 };
vector B = { 6, 7, 8, 9 };
vector C = { 10, 11, 12 };
// 调用函数进行合并
vector D = mergeThreeSortedArrays(A, B, C);
// 打印最终结果
cout << "合并后的数组: ";
for (int i = 0; i < D.size(); i++) {
cout << D[i] << " ";
}
cout << endl;
return 0;
}
Java 实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class MergeArraysNaive {
// 静态方法：合并三个列表并排序
static List mergeThreeSortedArrays(List A, List B, List C) {
List D = new ArrayList();
// 利用 addAll 方法一次性添加所有元素，代码更简洁
D.addAll(A);
D.addAll(B);
D.addAll(C);
// 使用 Collections.sort 进行原地排序
// 这里的时间复杂度为 O(N log N)
Collections.sort(D);
return D;
}
public static void main(String[] args) {
// 定义输入数据
List A = Arrays.asList(1, 2, 3, 5);
List B = Arrays.asList(6, 7, 8, 9);
List C = Arrays.asList(10, 11, 12);
// 执行合并操作
List D = mergeThreeSortedArrays(A, B, C);
// 输出结果
System.out.print("合并后的数组: ");
for (int i = 0; i < D.size(); i++) {
System.out.print(D.get(i) + " ");
}
System.out.println();
}
}
Python 实现
“INLINECODEe8e6af25`INLINECODE7c154b72iINLINECODE13468220jINLINECODE8393993fkINLINECODEeeace55eAINLINECODE6c19db02BINLINECODE4b605051CINLINECODEfa28b190DINLINECODE3e888551A[i]INLINECODE34c00dd2B[j]INLINECODE8ab1e0b3C[k]INLINECODEed0075a2DINLINECODE126d87b8AINLINECODE354b8ffcB 和 C`，而不应抛出异常或死循环。
总结
在这篇文章中，我们探讨了合并三个有序数组的问题。我们从最直观的“先合并后排序”方法入手，实现了多种语言版本，并分析了其时间复杂度。虽然这种方法简单直接，但我们了解到它忽略了输入数组的有序性，在大数据量下效率不够高。
更重要的是，我们引出了更高效的三指针解法，这才是面试和高级开发中期望看到的思路。通过这篇文章，希望你不仅学会了如何解决这个具体问题，更重要的是培养了分析时间复杂度和根据数据特性优化算法的思维习惯。
编程不仅仅是敲代码，更是对效率和逻辑的追求。下次当你面对有序数据时，记得想一想：我真的需要重新排序吗？还是可以直接利用它们现有的顺序？
继续练习，尝试手写一下那个 $O(N)$ 的优化解法吧！