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

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 static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] =
                (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
    return answer;}

利益点

1. 请注意，它所执行的操作数量与任何其他操作相同或更少。

   O(N)

   算法，但在字面上单语句在一个时间循环！
2. 如果两个数组的大小大致相同，则O(N)的常数是相同的。但是，如果数组确实不平衡，则使用

   System.arraycopy

   会赢，因为在内部，它可以使用单个x86程序集指令来完成这一任务。
3. 通知

   a[i] >= b[j]

   而不是

   a[i] > b[j]

   ..这保证了“稳定性”，即当a和b的元素相等时，我们希望a中的元素位于b之前。

Answer 2

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)  
       answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];

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


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

    return answer;}

是有点紧凑，但完全一样！