如何优化无额外空间下合并两个有序数组的代码？

原代码的性能瓶颈分析 #

你的现有实现思路是逐个检查arr1的元素，只要比arr2[0]大就交换，然后每次把arr2的最小值移到开头，最后再对arr2做选择排序。但这个方案的时间复杂度是O(n*m + m²)，当n和m的规模较大时（比如都是10^{4级别），运算量会暴增到10}8级别，性能表现会非常糟糕。

接下来我会介绍两种更高效的优化方案，都是原地操作（不使用额外空间），而且时间复杂度远低于原实现。

方案一：Gap法（基于Shell排序思想，最优原地合并方案）

这是目前原地合并两个有序数组最高效的方法之一，核心思路是把arr1和arr2看成一个长度为n+m的虚拟有序数组，通过逐步缩小的间隔（Gap）来比较并交换元素，最终让整个虚拟数组有序。此时arr1自然会存放合并后的前n个最小元素，arr2存放剩下的m个元素，完全符合题目要求。

具体实现步骤：

• 计算初始Gap：用(n + m + 1) // 2实现向上取整，确保初始间隔覆盖整个虚拟数组。
• 循环缩小Gap（每次gap = (gap + 1) // 2），直到Gap变为1并处理完成：
  • 遍历虚拟数组中所有间隔为Gap的元素对，根据元素所在的数组（都在arr1、跨数组、都在arr2）分别处理，若前一个元素大于后一个则交换。
• 当Gap缩小到1并处理完所有元素后，整个虚拟数组就完全有序了。

对应的Java代码实现：

class Solution {
    public void merge(int arr1[], int arr2[], int n, int m) {
        int totalLength = n + m;
        int gap = (totalLength + 1) / 2; // 初始向上取整的间隔
        
        while (gap > 0) {
            int i = 0;
            // 遍历所有间隔为gap的元素对
            while (i + gap < totalLength) {
                int j = i + gap;
                if (i < n && j < n) {
                    // 两个元素都在arr1中
                    if (arr1[i] > arr1[j]) {
                        swap(arr1, i, j);
                    }
                } else if (i < n && j >= n) {
                    // i在arr1，j在arr2
                    int jArr2 = j - n;
                    if (arr1[i] > arr2[jArr2]) {
                        swap(arr1, arr2, i, jArr2);
                    }
                } else {
                    // 两个元素都在arr2中
                    int iArr2 = i - n;
                    int jArr2 = j - n;
                    if (arr2[iArr2] > arr2[jArr2]) {
                        swap(arr2, iArr2, jArr2);
                    }
                }
                i++;
            }
            // 当gap为1时，处理完即可退出，避免死循环
            if (gap == 1) {
                break;
            }
            gap = (gap + 1) / 2; // 再次向上取整缩小间隔
        }
    }
    
    // 交换同一数组内的两个元素
    private void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
    
    // 交换arr1和arr2中的元素
    private void swap(int[] arr1, int[] arr2, int idx1, int idx2) {
        int temp = arr1[idx1];
        arr1[idx1] = arr2[idx2];
        arr2[idx2] = temp;
    }
}

这个方案的优势：

• 时间复杂度为O((n+m)log(n+m))，相比原实现的O(nm+m²)，效率提升几个数量级。
• 完全不需要额外空间，严格符合题目要求。
• 最终结果自动满足arr1存前n个最小元素、arr2存剩余元素的要求，无需额外拆分。

方案二：双指针+插入排序（更直观的优化）

如果觉得Gap法的思路有点绕，也可以用更直观的双指针思路优化原实现：

• 用指针i遍历arr1，指针j指向arr2的开头。
• 当arr1[i] > arr2[j]时，交换两者，然后对arr2进行插入排序（因为arr2原本是有序的，只有arr2[0]的位置不对，插入排序只需要移动少量元素就能归位，比原实现的全遍历找最小值高效）。
• 遍历完arr1后，arr2本身已经有序，不需要再做选择排序。

对应的Java代码：

class Solution {
    public void merge(int arr1[], int arr2[], int n, int m) {
        for (int i = 0; i < n; i++) {
            if (arr1[i] > arr2[0]) {
                // 交换arr1[i]和arr2[0]
                int temp = arr1[i];
                arr1[i] = arr2[0];
                arr2[0] = temp;
                
                // 对arr2进行插入排序，把arr2[0]放到正确位置
                int key = arr2[0];
                int j = 1;
                while (j < m && arr2[j] < key) {
                    arr2[j-1] = arr2[j];
                    j++;
                }
                arr2[j-1] = key;
            }
        }
    }
}

这个方案的时间复杂度是O(n*m)，虽然比Gap法差，但相比原实现的O(nm+m²)还是优化了，而且思路更直观，容易理解。

总结 #

如果追求最优性能，优先选择Gap法；如果需要更直观的实现，可以选择双指针+插入排序的方案。两种方案都满足题目“不使用额外空间”的要求，且最终结果完全符合示例中的输出规范。

内容的提问来源于stack exchange，提问作者Shivam Mishra