如何在不使用额外数组/集合空间的前提下对两个数组整体排序？

核心思路 #

由于禁止使用额外数组或集合，所有操作必须在原数组内完成，核心流程分为三步：

1. 分别对两个数组执行原地升序排序（选用无需额外空间的排序算法，如冒泡、插入排序）。
2. 双指针交换错位元素：用指针指向arr1的末尾（当前最大元素）和arr2的开头（当前最小元素），若arr1的元素更大则交换，确保arr1整体元素小于等于arr2。
3. 再次分别对两个数组执行原地升序排序，最终得到前小后大的有序数组。

代码实现（Java） #

首先实现原地冒泡排序：

// 原地升序排序数组，无额外空间开销
private static void bubbleSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 临时变量仅用于交换，不属于额外数组/集合
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

主逻辑实现：

public static void mergeSortWithoutExtraSpace(int[] arr1, int[] arr2) {
    int arr1Len = arr1.length;
    int arr2Len = arr2.length;

    // 步骤1：分别排序两个数组
    bubbleSort(arr1);
    bubbleSort(arr2);

    // 步骤2：双指针交换错位元素
    int i = arr1Len - 1; // arr1末尾（最大元素位置）
    int j = 0;           // arr2开头（最小元素位置）
    while (i >= 0 && j < arr2Len) {
        if (arr1[i] > arr2[j]) {
            // 交换元素，让小元素去arr1，大元素去arr2
            int temp = arr1[i];
            arr1[i] = arr2[j];
            arr2[j] = temp;
            i--;
            j++;
        } else {
            // 此时arr1所有元素都<=arr2元素，无需继续交换
            break;
        }
    }

    // 步骤3：再次分别排序，确保两个数组各自有序
    bubbleSort(arr1);
    bubbleSort(arr2);
}

测试示例 #

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

    mergeSortWithoutExtraSpace(arr1, arr2);

    // 输出结果
    System.out.print("arr1 = [");
    for (int k = 0; k < arr1.length; k++) {
        if (k > 0) System.out.print(",");
        System.out.print(arr1[k]);
    }
    System.out.println("]");

    System.out.print("arr2 = [");
    for (int k = 0; k < arr2.length; k++) {
        if (k > 0) System.out.print(",");
        System.out.print(arr2[k]);
    }
    System.out.println("]");
}

降序排序适配 #

若需要降序输出，只需修改三处：

1. 冒泡排序的比较条件改为arr[j] < arr[j+1]（降序排序）。
2. 双指针交换条件改为arr1[i] < arr2[j]（把arr1的小数和arr2的大数交换）。
3. 步骤3再次执行降序排序。

合规性说明 #

• 全程未创建额外数组或集合，仅使用单个临时变量用于元素交换，符合空间限制要求。
• 两个数组的长度始终保持初始值，未做修改。

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