合并两个有序数组（Java + Python）

给定两个有序数组arr1和arr2，将两个数组合并成一个有序数组。

arr1 = [1, 3, 5]
arr2 = [2, 4, 8, 9]
输出：[1, 2, 3, 4, 5, 8, 9]

思路：

1、合并后排序，都能想到的。（不采用）
2、两个数组都是有序的，按顺序比较大小即可。

可用类似归并排序的思路，声明两个数组索引指针，分别遍历两个数组，比较值的大小，将较大（小）的值放到目标数组中，继续遍历。
Java：

public static void main(String[] arg){
        int[] arr1 = {1,  3, 5};
        int[] arr2 = {2, 4, 8, 9};
        int[] arrs = new int[arr1.length + arr2.length];
        int i = arr1.length - 1, j = arr2.length - 1, k = arr1.length + arr2.length -1;
        while (i >= 0 && j >= 0){
            arrs[k--] = arr1[i] >= arr2[j] ? arr1[i--] : arr2[j--];
        }
        while (i >= 0){
            arrs[k--] = arr1[i--];
        }
        while (j >= 0){
            arrs[k--] = arr2[j--];
        }

        System.out.println(Arrays.toString(arrs));
    }

Python：

def Order_sort(arr1, arr2):
    rel = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            rel.append(arr1[i])
            i += 1
        else:
            rel.append(arr2[j])
            j += 1
    while i < len(arr1):
        rel.append(arr1[i])
        i += 1
    while j < len(arr2):
        rel.append(arr2[j])
        j += 1
    return rel


if __name__ == '__main__':
    arr1 = [1, 3, 5, 8, 10]
    arr2 = [2, 4, 8, 9]
    print(Order_sort(arr1, arr2))

输出：[1, 2, 3, 4, 5, 8, 8, 9, 10]

合并到新数组可以从头、从尾遍历皆可。后面两个循环考虑arr1和arr2有剩余的两种情况，把数组中剩余的元素赋值到新数组中。Python还可以每次循环都是比较第一个元素或最后一个元素，将需要的元素赋值到新列表中后删除，继续遍历。