如何在 Java 中合并两个有序数组

1. 简介

本文将介绍如何将两个已排序的数组合并为一个有序数组。这是一个经典的基础算法问题，常见于面试和实际开发中的数据合并场景。

2. 问题描述

我们有两个升序排列的整型数组，目标是将它们合并成一个更大的升序数组。

Merge Sorted Arrays

例如：

数组 A：[3, 7]
数组 B：[4, 8, 11]
合并结果：[3, 4, 7, 8, 11]

关键点在于：两个输入数组本身是有序的，我们要利用这个特性，避免重新排序带来的性能损耗。

3. 算法思路

这个问题其实可以看作是归并排序（Merge Sort）中“合并”阶段的简化版 ✅。核心思想是使用双指针技巧（Two Pointers），从两个数组头部开始比较，逐个选择较小的元素放入结果数组。

核心步骤：

定义两个指针 fooPosition 和 barPosition，分别指向两个数组的当前处理位置
定义一个结果数组 merged，长度为两数组之和
使用循环同时遍历两个数组：
- 比较当前两个指针所指元素
- 将较小者复制到结果数组，并移动对应指针
当其中一个数组遍历完后，直接将另一个数组剩余元素全部拷贝过去

图解过程

Step 1：
比较 foo[0]=3 和 bar[0]=4，3 更小，选它。

Merge Arrays First Step

fooPosition 向前移动一位。

Step 2：
比较 foo[1]=7 和 bar[0]=4，4 更小，选它。

Merge Arrays Second Step

barPosition 向前移动一位。

Step 3：
继续比较，7 < 8，选 7。

Merge Arrays Third Step

此时 foo 数组已全部处理完毕。

Step 4：
将 bar 中剩余元素（8, 11）全部复制到结果中。

Merge Arrays Fourth Step

合并完成 ✅。

4. 代码实现

public static int[] merge(int[] foo, int[] bar) {

    int fooLength = foo.length;
    int barLength = bar.length;

    int[] merged = new int[fooLength + barLength];

    int fooPosition, barPosition, mergedPosition;
    fooPosition = barPosition = mergedPosition = 0;

    // 双指针合并主循环
    while (fooPosition < fooLength && barPosition < barLength) {
        if (foo[fooPosition] < bar[barPosition]) {
            merged[mergedPosition++] = foo[fooPosition++];
        } else {
            merged[mergedPosition++] = bar[barPosition++];
        }
    }

    // 拷贝 foo 剩余元素
    while (fooPosition < fooLength) {
        merged[mergedPosition++] = foo[fooPosition++];
    }

    // 拷贝 bar 剩余元素
    while (barPosition < barLength) {
        merged[mergedPosition++] = bar[barPosition++];
    }

    return merged;
}

单元测试

@Test
void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() {

    int[] foo = { 3, 7 };
    int[] bar = { 4, 8, 11 };
    int[] merged = { 3, 4, 7, 8, 11 };

    assertArrayEquals(merged, SortedArrays.merge(foo, bar));
}

✅ 测试通过，结果符合预期。

⚠️ 注意：该实现假设输入数组非空且已排序。实际项目中建议加上空值校验（null check）和有序性验证（可选），避免踩坑。

5. 复杂度分析

时间复杂度： O(m + n)
每个元素仅被访问一次，m 和 n 分别为两个数组的长度。
空间复杂度： O(m + n)
需要额外数组存储合并结果。

🔍 提示：如果允许修改原数组或使用链表结构，可能优化空间使用，但本题最直观解法就是新建数组。

6. 总结

合并两个有序数组是一个简单但高频的问题，掌握其双指针解法对理解归并排序、归并链表等问题非常有帮助。

✅ 关键点回顾：

利用“已排序”特性，避免重新排序
双指针同步推进，每次选最小元素
任一数组结束后，剩余部分直接追加

源码示例可在 GitHub 获取：https://github.com/eugenp/tutorials/tree/master/algorithms-modules/algorithms-miscellaneous-5

Persistence

REST

Security