Java 合并两个已排序的数组

如何合并两个已排序数组至单个新的排序数组。

算法

假设有两个已排序数组 arr1 和 arr2，长度分别为len1、len2。接着我们定义结果数组，长度为len1+len2。
我们在同一个循环中便利两个数组，通过对每个数组维护一个位置索引post1和post2。对于每个迭代，比较两个数组元素，较小的元素存入结果数组中，对应数组的位置索引移动至下一个。

直到遍历完其中一个数组的所有元素，最后拷贝另一个数组中余下的元素至结果数组中。

实现过程

下面给java实现代码，结合上述算法描述增加了注释。

public static int[] merge(int[] arr1, int[] arr2) { 
    int len1 = arr1.length; 
    int len2 = arr2.length; 
 
    // 定义结果数组 
    int[] merged = new int[len1 + len2]; 
 
    // 定义索引位置 
    int loc1, loc2, mergedLoc; 
    loc1 = loc2 = mergedLoc = 0; 
 
    // 遍历两个数组 
    while(loc1 < len1 && loc2 < len2) { 
        if (arr1[loc1] < arr2[loc2]) { 
            merged[mergedLoc++] = arr1[loc1++]; 
        } else { 
            merged[mergedLoc++] = arr2[loc2++]; 
        } 
    } 
 
    // 拷贝较长数组余下的元素 
    while (loc1 < len1) { 
        merged[mergedLoc++] = arr1[loc1++]; 
    } 
 
    while (loc2 < len2) { 
        merged[mergedLoc++] = arr2[loc2++]; 
    } 
 
    return merged; 
} 

时间复杂度

我们便利两个数组并选择较小的元素。最后拷贝较长数组余下的元素。所以时间复杂度为O(len1 + len2)。因为使用辅助数组存储结果，因此空间复杂度也是O(len1 + len2)。

本文参考链接：https://blog.csdn.net/neweastsun/article/details/115246063