排序算法之：合并排序数组（Merge Sorted Arrays）的“从后向前”尾插法与原地合并优化

题目描述
给定两个有序整数数组 nums1 和 nums2，以及两个整数 m 和 n，分别表示 nums1 和 nums2 中的有效元素数量。假设 nums1 的长度为 m + n，其前 m 个元素为有效元素，后 n 个元素为占位符（通常初始化为 0）。要求将 nums2 合并到 nums1 中，使得合并后的数组仍然保持非递减顺序。必须原地修改 nums1，不能使用额外的数组空间。

示例：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：合并后数组包含前 3 个元素来自 nums1 和后 3 个元素来自 nums2，且整个数组有序。

解题过程循序渐进讲解

步骤1：问题分析与常规思路的局限性

• 由于需要原地合并，最直接的思路可能是从两个数组的开头进行比较，将 nums2 的元素插入 nums1 的合适位置。但这样做会面临一个问题：当把 nums2 的元素插入 nums1 的前部时，为了给新元素腾出位置，需要将 nums1 中已有的元素向后移动，导致大量数据搬迁，时间复杂度为 O(m*n)，效率极低。
• 另一个思路是先用额外数组存储合并结果，再复制回 nums1，但题目要求原地操作，且希望空间复杂度为 O(1)（不计返回数组占用的空间）。

步骤2：关键洞察——从后向前合并

• 注意到 nums1 的尾部有 n 个空位（占位符 0）。如果我们从两个数组的有效元素末尾开始比较，选择较大的元素放到 nums1 的整个数组末尾，就可以避免覆盖 nums1 中尚未处理的元素。
• 具体来说：
  1. 设三个指针：
     • i 指向 nums1 有效部分的最后一个元素（索引 m-1）。
     • j 指向 nums2 的最后一个元素（索引 n-1）。
     • k 指向 nums1 的最后一个位置（索引 m+n-1），用于放置当前比较得到的较大元素。
  2. 比较 nums1[i] 和 nums2[j]：
     • 如果 nums1[i] >= nums2[j]，将 nums1[i] 放到 nums1[k]，然后 i-- 和 k--。
     • 否则，将 nums2[j] 放到 nums1[k]，然后 j-- 和 k--。
  3. 重复步骤2，直到 i 或 j 其中一个小于 0。
  4. 如果 j >= 0，说明 nums2 中还有剩余元素（这些元素是当前最小的），直接按顺序复制到 nums1 的前部（位置 0 到 k）。

步骤3：逐步推演示例
初始状态：
nums1 = [1, 2, 3, 0, 0, 0] m=3
nums2 = [2, 5, 6] n=3
i=2 (指向3), j=2 (指向6), k=5

第1轮：比较 nums1[2]=3 和 nums2[2]=6 → 6 更大 → nums1[5]=6, j=1, k=4
nums1 变为 [1,2,3,0,0,6]

第2轮：比较 nums1[2]=3 和 nums2[1]=5 → 5 更大 → nums1[4]=5, j=0, k=3
nums1 变为 [1,2,3,0,5,6]

第3轮：比较 nums1[2]=3 和 nums2[0]=2 → 3 更大 → nums1[3]=3, i=1, k=2
nums1 变为 [1,2,3,3,5,6]

第4轮：比较 nums1[1]=2 和 nums2[0]=2 → 相等（或认为 nums1[1] 更大）→ nums1[2]=2, i=0, k=1
nums1 变为 [1,2,2,3,5,6]

第5轮：比较 nums1[0]=1 和 nums2[0]=2 → 2 更大 → nums1[1]=2, j=-1, k=0
nums1 变为 [1,2,2,3,5,6]

此时 j=-1，nums2 已空，合并完成。

步骤4：边界情况处理

• 如果 m=0（即 nums1 初始无有效元素），则直接复制 nums2 到 nums1 的前 n 个位置。
• 如果 n=0（即 nums2 为空），则 nums1 已经是结果，无需操作。
• 上述算法在 nums2 有剩余时（j>=0）需要单独处理复制，这是因为这些剩余元素比 nums1 中所有已放置的元素都小，应放在最前面。

步骤5：时间复杂度与空间复杂度分析

• 每个元素最多被比较和移动一次，因此总操作次数为 m+n。
• 时间复杂度：O(m+n)，线性时间，非常高效。
• 空间复杂度：O(1)，只用了几个指针变量，满足原地修改要求。

步骤6：代码实现（伪代码）

function merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    
    while i >= 0 and j >= 0:
        if nums1[i] >= nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    // 如果 nums2 还有剩余元素（即 j >= 0）
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

注意：当 j>=0 时复制剩余元素，不需要再处理 i>=0 的情况，因为如果 nums1 有剩余，它们已经在正确位置了。

步骤7：进一步思考与扩展

• 为什么从后向前能避免覆盖？因为 nums1 尾部的空位是“安全区”，从大到小填充不会影响到尚未比较的 nums1 元素。
• 此方法本质上是双指针尾插法，利用了输入数组已有序的特性，是合并两个有序数组的最优解法之一。
• 如果问题变体要求稳定排序（即相等元素保持原有顺序），上述代码中当 nums1[i] == nums2[j] 时，优先放置 nums1[i] 可以保持 nums1 元素的相对顺序，但 nums2 元素会放在其后。如需完全稳定，可根据题目定义调整。