如何将两个排序数组合并为排序数组？

Question

如何将两个排序数组合并为排序数组？

这是我在一次面试中被问到的，这就是我提供的解决方案：

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
    {
        if (a[i] < b[j])
        {
            answer[k] = a[i];
            i++;
        }
        else
        {
            answer[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < a.length)
    {
        answer[k] = a[i];
        i++;
        k++;
    }

    while (j < b.length)
    {
        answer[k] = b[j];
        j++;
        k++;
    }

    return answer;}

有更有效的方法吗？

编辑：修正长度方法。

Answer 1

我感到惊讶的是，没有人提到这种更酷、更高效、更紧凑的实现：public&nbsp;static&nbsp;int[]&nbsp;merge(int[]&nbsp;a,&nbsp;int[]&nbsp;b)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;answer&nbsp;=&nbsp;new&nbsp;int[a.length&nbsp;+&nbsp;b.length]; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i&nbsp;=&nbsp;a.length&nbsp;-&nbsp;1,&nbsp;j&nbsp;=&nbsp;b.length&nbsp;-&nbsp;1,&nbsp;k&nbsp;=&nbsp;answer.length; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(k&nbsp;>&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer[--k]&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(j&nbsp;<&nbsp;0&nbsp;||&nbsp;(i&nbsp;>=&nbsp;0&nbsp;&&&nbsp;a[i]&nbsp;>=&nbsp;b[j]))&nbsp;?&nbsp;a[i--]&nbsp;:&nbsp;b[j--]; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;answer;}利益点请注意，它所执行的操作数量与任何其他操作相同或更少。O(N)算法，但在字面上单语句在一个时间循环！如果两个数组的大小大致相同，则O(N)的常数是相同的。但是，如果数组确实不平衡，则使用System.arraycopy会赢，因为在内部，它可以使用单个x86程序集指令来完成这一任务。通知a[i] >= b[j]而不是a[i] > b[j]..这保证了“稳定性”，即当a和b的元素相等时，我们希望a中的元素位于b之前。

Answer 2

public&nbsp;static&nbsp;int[]&nbsp;merge(int[]&nbsp;a,&nbsp;int[]&nbsp;b)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;int[]&nbsp;answer&nbsp;=&nbsp;new&nbsp;int[a.length&nbsp;+&nbsp;b.length]; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i&nbsp;=&nbsp;0,&nbsp;j&nbsp;=&nbsp;0,&nbsp;k&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(i&nbsp;<&nbsp;a.length&nbsp;&&&nbsp;j&nbsp;<&nbsp;b.length)&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer[k++]&nbsp;=&nbsp;a[i]&nbsp;<&nbsp;b[j]&nbsp;?&nbsp;a[i++]&nbsp;:&nbsp;&nbsp;b[j++]; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(i&nbsp;<&nbsp;a.length)&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer[k++]&nbsp;=&nbsp;a[i++]; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(j&nbsp;<&nbsp;b.length)&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer[k++]&nbsp;=&nbsp;b[j++]; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;answer;}是有点紧凑，但完全一样！