排序算法之：合并两个有序数组的“尾插法”与原地合并优化

题目描述

给定两个按非递减顺序排列的整数数组 nums1 和 nums2，以及两个整数 m 和 n，分别表示 nums1 和 nums2 中的有效元素数量。
假设 nums1 的长度为 m + n，其前 m 个元素为有效元素，后 n 个位置初始化为0（或其他占位值）。
请将 nums2 合并到 nums1 中，使合并后的数组同样保持非递减顺序。
要求：直接在 nums1 上原地合并，不使用额外的数组空间。

逐步解题过程

1. 理解问题与约束

• 目标是合并两个已排序的数组。
• 必须原地修改 nums1，不能申请额外数组。
• nums1 的长度足够容纳所有元素（长度为 m + n）。
• 难点：如果从前往后合并，可能会覆盖 nums1 中尚未处理的元素。

示例：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

2. 初步思路：暴力插入的缺陷

如果尝试从前往后合并，比较 nums1[i] 和 nums2[j]，将较小的放入当前位置，会出现覆盖问题。
例如，比较 nums1[0]=1 和 nums2[0]=2，1 更小，保留原位。下一步比较 nums1[1]=2 和 nums2[0]=2，如果直接将 2 放入 nums1[1]，没问题，但后续遇到需要将 nums2 的元素插入到 nums1 中间时，必须将 nums1 后面的元素全部后移，时间复杂度会退化到 O(mn)，效率很低。

3. 核心优化思路：从后向前合并（尾插法）

因为 nums1 的后半部分是空闲的（初始为0），我们可以从两个数组的末尾开始比较，将较大的元素依次放入 nums1 的末尾。
这样，不会覆盖 nums1 中尚未处理的元素，因为空闲位置始终足够。

具体步骤：

• 设置三个指针：
  • p1：指向 nums1 的最后一个有效元素（索引 m-1）。
  • p2：指向 nums2 的最后一个元素（索引 n-1）。
  • p：指向 nums1 的最后一个位置（索引 m+n-1）。
• 比较 nums1[p1] 和 nums2[p2]，将较大的值放入 nums1[p]，然后将对应的指针向左移动一位，p 也向左移动一位。
• 重复直到某个数组的所有元素都被处理完。
• 如果 nums2 中还有剩余元素，直接复制到 nums1 的前面。

为什么可行？

• 因为从后向前填充，nums1 中已处理的元素位置不会被覆盖。
• 由于两个数组都已排序，每次取当前最大的元素放到末尾，能保证最终数组有序。

4. 详细算法步骤

1. 初始化 p1 = m - 1, p2 = n - 1, p = m + n - 1。
2. 当 p1 >= 0 且 p2 >= 0 时循环：
   • 如果 nums1[p1] > nums2[p2]：
     • 将 nums1[p1] 赋值给 nums1[p]。
     • p1--。
   • 否则：
     • 将 nums2[p2] 赋值给 nums1[p]。
     • p2--。
   • p--。
3. 如果 p2 >= 0，说明 nums2 中还有剩余元素（这些元素是当前最小的），将它们复制到 nums1[0] 到 nums1[p] 的位置。
   • 注意：复制时可以使用 while (p2 >= 0) { nums1[p] = nums2[p2]; p--; p2--; }。

5. 演示例子

输入：

nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3

步骤：

• 初始：p1=2, p2=2, p=5
• 比较 nums1[2]=3 和 nums2[2]=6 → 6 大 → nums1[5]=6, p2=1, p=4
• 比较 nums1[2]=3 和 nums2[1]=5 → 5 大 → nums1[4]=5, p2=0, p=3
• 比较 nums1[2]=3 和 nums2[0]=2 → 3 大 → nums1[3]=3, p1=1, p=2
• 比较 nums1[1]=2 和 nums2[0]=2 → 相等（取哪个都行，假设取 nums2）→ nums1[2]=2, p2=-1, p=1
• 此时 p2=-1，结束循环。nums1 已是 [1,2,2,3,5,6]。

6. 时间复杂度与空间复杂度分析

• 时间复杂度：O(m + n)。
  每个元素只被比较和移动一次。
• 空间复杂度：O(1)。
  只使用了常数个额外指针，是严格的原地操作。

7. 边界情况考虑

• 如果 m = 0：直接复制 nums2 到 nums1。
• 如果 n = 0：nums1 已经是结果，无需操作。
• 如果 nums1 的所有元素都大于 nums2 的所有元素：
  例如 nums1 = [7,8,9,0,0,0], nums2 = [1,2,3]，经过循环后，nums2 的剩余元素会被复制到 nums1 开头。
• 如果 nums2 的所有元素都大于 nums1 的所有元素：
  例如 nums1 = [1,2,3,0,0,0], nums2 = [4,5,6]，循环中会逐步将 nums2 的元素放到末尾，最后 nums1 的元素自然在前面，无需额外复制。

8. 代码实现（Python示例）

def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, m + n - 1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    # 如果 nums2 还有剩余元素
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p -= 1
        p2 -= 1

总结

• 本题的优化核心是从后向前合并，利用 nums1 后半部分的空闲空间，避免数据覆盖。
• 这种方法既保证了时间效率 O(m+n)，又满足了原地操作的要求。
• 是合并两个有序数组的经典技巧，在多种场景（如归并排序的最后一步）中有广泛应用。