java一次排序2个数组，无需额外空间

Question

我应该如何优化我的代码

Given two sorted arrays arr1[] of size N and arr2[] of size M. Each array is sorted in non-decreasing order. Merge the two arrays into one sorted array in non-decreasing order without using any extra space.

Example 1:

Input:

N = 4, M = 5
arr1[] = {1, 3, 5, 7}
arr2[] = {0, 2, 6, 8, 9}

Output:

0 1 2 3 5 6 7 8 9

Explanation: Since you can't use any extra space, modify the given arrays to form:

arr1[] = {0, 1, 2, 3}
arr2[] = {5, 6, 7, 8, 9}

class Solution {
    public void merge(int arr1[], int arr2[], int n, int m) {
        for (int k = 0; k < n; k++) {
            boolean c = false;
            if (arr1[k] > arr2[0]) {
                int temp = arr1[k];
                arr1[k] = arr2[0];
                arr2[0] = temp;
                c = true;
            }
            if (c) {
                int minIndex = 0;
                for (int i = 0; i < m; i++) {
                    if (arr2[i] < arr2[minIndex])
                        minIndex = i;
                }
                int t = arr2[minIndex];
                arr2[minIndex] = arr2[0];
                arr2[0] = t;
            }
        }
        for (int i = 0; i < m - 1; i++) {
            int minIndex = i;
            for (int j = i; j < m; j++) {
                if (arr2[j] < arr2[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr2[i];
            arr2[i] = arr2[minIndex];
            arr2[minIndex] = temp;
        }
    }
}

Answer 1

由于不能使用任何额外的空间，因此可以同时对这两个数组执行一种选择排序n + m，同时检查每个索引是否已在第二个数组中：

public static void main(String[] args) {
    int[] arr1 = {1, 3, 5, 7};
    int[] arr2 = {0, 2, 6, 8, 9};

    selectionSort(arr1, arr2);

    System.out.println(Arrays.toString(arr1)); // [0, 1, 2, 3]
    System.out.println(Arrays.toString(arr2)); // [5, 6, 7, 8, 9]
}

public static void selectionSort(int[] arr1, int[] arr2) {
    int n = arr1.length;
    int m = arr2.length;
    for (int i = 0; i < n + m; i++) {
        int min = i < n ? arr1[i] : arr2[i - n];
        int min_i = i;
        for (int j = i + 1; j < n + m; j++)
            if (j < n ? arr1[j] < min : arr2[j - n] < min) {
                min = j < n ? arr1[j] : arr2[j - n];
                min_i = j;
            }
        if (i != min_i)
            if (i < n) {
                int temp = arr1[i];
                if (min_i < n) {
                    arr1[i] = arr1[min_i];
                    arr1[min_i] = temp;
                } else {
                    arr1[i] = arr2[min_i - n];
                    arr2[min_i - n] = temp;
                }
            } else {
                int temp = arr2[i - n];
                if (min_i < n) {
                    arr2[i - n] = arr1[min_i];
                    arr1[min_i] = temp;
                } else {
                    arr2[i - n] = arr2[min_i - n];
                    arr2[min_i - n] = temp;
                }
            }
    }
}

---

^{另见：Java Selection Sort}

Answer 2

这是一个稍微简单的版本。它仍然具有相同的二次时间复杂度O（n*m），但执行速度比发布的代码快10倍，因此它确实符合优化版本：

class Solution {
    public void merge_chqrlie(int arr1[], int arr2[], int n, int m) {
        if (n > 0 && m > 0) {
            // for each element of arr2
            for (int i1 = 0, i2 = 0, j, k = 0; k < m; k++) {
                // shift it left inside arr2
                for (j = k; j > i2 && arr2[j-1] > arr2[j]; j ) {
                    int temp = arr2[j-1];
                    arr2[j-1] = arr2[j];
                    arr2[j] = temp;
                }
                // if it moved to arr2[0] and is smaller than the last element of arr1
                if (j == 0 && arr1[n-1] > arr2[0]) {
                    // move it to arr1[n-1]
                    int temp = arr1[n-1];
                    arr1[n-1] = arr2[0];
                    arr2[0] = temp;
                    // and further shift it into arr1
                    for (j = n - 1; j > i1 && arr1[j-1] > arr1[j]; j ) {
                        temp = arr1[j-1];
                        arr1[j-1] = arr1[j];
                        arr1[j] = temp;
                    }
                    // update i1: the finalized portion of arr1
                    i1 = j + 1;
                } else {
                    // update i2: the finalized portion of arr2
                    i2 = j + 1;
                }
            }
        }
    }
}

不使用额外空间的合并是一个非常严格的约束：你认为局部变量是额外的空间吗？如果您考虑到有限的额外空间，例如128个元素的单个数组，则可以找到速度更快的解决方案，其执行速度比发布的中等大小数组（超过5000个元素）的代码快500到2000倍，但对于大型数组，仍然表现出二次时间复杂性

这是一个高级解决方案（对于500k单元阵列，速度快1000倍）：

class Solution {
    static int tmp_size = 128;
    static int *tmp;
    public void merge_chqrlie2(int arr1[], int arr2[], int n, int m) {
        if (!tmp)
            tmp = new int[tmp_size];
        for (int chunk = tmp_size; n > 0; n -= chunk, arr1 += chunk) {
            int i = 0, j = 0, k = 0;
            if (chunk > n)
                chunk = n;
            for (k = 0; k < chunk; k++)
                tmp[k] = arr1[k];
    
            for (k = 0; k < chunk; k++) {
                if (j >= m || tmp[i] <= arr2[j])
                    arr1[k] = tmp[i++];
                else
                    arr1[k] = arr2[j++];
            }
            for (k = 0; i < chunk; k++) {
                if (j >= m || tmp[i] <= arr2[j])
                    arr2[k] = tmp[i++];
                else
                    arr2[k] = arr2[j++];
            }
        }
    }
}

临时存储将以C或C++等语言分配给堆栈（自动存储），以达到最佳效率。p>

这是一个更有效的方法，在病理样本上的性能更好，在随机内容上的速度更快2.5倍：

void merge_chqrlie3(int arr1[], int arr2[], size_t n, size_t m) {
    int tmp[128];
    size_t i2 = 0;

    for (size_t chunk = sizeof(tmp) / sizeof(*tmp); n > 0; n -= chunk, arr1 += chunk) {
        size_t i = 0, j = 0, k = 0;

        if (i2 == 0) {
            while (n > 0 && arr1[0] <= arr2[0]) {
                arr1++;
                n ;
            }
        }
        if (chunk > n)
            chunk = n;

        for (k = 0; k < chunk; k++)
            tmp[k] = arr1[k];

        if (chunk <= i2) {
            for (j = 0; j < chunk; j++)
                arr1[j] = arr2[j];
            for (k = 0; j < i2; k++)
                arr2[k] = arr2[j++];
        } else {
            for (k = 0; j < i2; k++)
                arr1[k] = arr2[j++];
            for (; k < chunk; k++) {
                if (j >= m || tmp[i] <= arr2[j])
                    arr1[k] = tmp[i++];
                else
                    arr1[k] = arr2[j++];
            }
            k = 0;
        }
        for (; i < chunk; k++) {
            if (j >= m || tmp[i] <= arr2[j])
                arr2[k] = tmp[i++];
            else
                arr2[k] = arr2[j++];
        }
        i2 = k;
    }
}

减少临时存储大小几乎线性地降低了执行时间：merge_chrlie2仍然比使用12个元素的本地数组发布的代码快100倍，这很难被视为额外存储

我在C中运行了一个基准测试，使用无空间合并函数作为经典的自顶向下递归合并排序的合并阶段。以下是包含128个元素的临时数组的计时（*）：

        size        malloc      chqrlie3      chqrlie2       chqrlie        shivam
        1000         0.059         0.064         0.064         0.252         2.010
        2000         0.153         0.124         0.126         0.836         7.872
        5000         0.441         0.505         0.528         5.218        49.947
       10000         0.667         0.769         0.898        19.850       205.316
       20000         1.531         1.917         2.195        85.185       812.061
       50000         4.036         6.123         9.244       524.873      5197.808
      100000         8.281        15.466        28.787      2064.165     20485.584
      200000        18.030        51.438       106.391      8342.140     82226.825
      500000        49.201       246.224       557.470     51982.830    511418.600
     1000000       112.594       915.575      2171.953    207096.552   2053797.858
     2000000       215.045      3883.104      8476.783    829806.868   8153974.589
     5000000       565.701     34142.299     67304.217   5855744.544  51565024.699

以下是仅包含5个元素的临时数组的计时：

        size        malloc      chqrlie3      chqrlie2       chqrlie        shivam
        1000         0.055         0.089         0.111         0.230         1.963
        2000         0.165         0.247         0.327         0.880         7.891
        5000         0.438         1.309         1.914         4.971        50.376
       10000         0.799         2.832         5.675        21.544       202.929
       20000         1.589         9.265        23.528        82.582       826.768
       50000         4.150        53.408       131.302       519.007      5089.592
      100000         8.375       205.644       533.308      2016.670     20431.584
      200000        17.291       797.865      2193.575      9536.996     82308.875
      500000        61.955      6565.826     15626.427     50813.910    508269.938
     1000000       105.836     21146.977     52530.060    205640.244   2036022.030

---

（*）以毫秒为单位的计时，分别为大于50k和200k的数组的chqrlie和shivam外推