排序算法之：双指针法在“合并两个有序数组”中的原地合并优化策略

我们来看一个经典的问题：有两个有序数组（或一个数组的两部分），要求将它们合并成一个大的有序数组。最常见的形式是“合并两个有序数组”（Merge Sorted Array），通常描述为：给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。nums1 的长度为 m + n，其中前 m 个元素是有效的，后 n 个元素被置为 0（或其他占位符）。请你将 nums2 合并入 nums1，使得合并后的数组也按非递减顺序排列。要求算法是 原地 的，即不借助额外的、与输入规模相当的空间。

题目描述

核心要求是：将 nums2（长度为 n）的所有元素合并到 nums1（总长度为 m + n，其中有效部分长度为 m）中，并保持 nums1 在合并后整体有序。已知 nums1 和 nums2 初始都是非递减排序的。

常规的合并方法会使用一个新数组，然后从两个数组头部开始取较小元素放入新数组，最后再复制回 nums1。但这样需要 O(m + n) 的额外空间。我们的目标是原地合并，即在不使用额外数组的情况下完成合并，空间复杂度应为 O(1)。

解题思路分析

关键洞察：
nums1 的后 n 个位置是空的（初始值为 0 或无意义），这是一个可以使用的“缓冲区”。如果我们从两个数组的尾部（即最大值）开始向前比较，并将较大的数放到 nums1 的尾部（从索引 m + n - 1 开始），就不会覆盖 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 < 0 或 j < 0。
4. 处理剩余元素：
   • 如果 nums1 还有剩余（即 i >= 0），它们已经在正确位置，无需移动。
   • 如果 nums2 还有剩余（即 j >= 0），说明这些元素是整体中最小的，依次复制到 nums1 的前部（从 k 开始向前填充）。

详细讲解与例子

假设：

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

初始化：

• i = 2 (指向 nums1[2] = 5)
• j = 2 (指向 nums2[2] = 6)
• k = 5 (指向 nums1[5])

第一步： 比较 5 和 6，6 更大，所以 nums1[5] = 6，j=1, k=4。
nums1 变为 [1, 3, 5, 0, 0, 6]

第二步： 比较 5 和 4，5 更大，所以 nums1[4] = 5，i=1, k=3。
nums1 变为 [1, 3, 5, 0, 5, 6]

第三步： 比较 3 和 4，4 更大，所以 nums1[3] = 4，j=0, k=2。
nums1 变为 [1, 3, 5, 4, 5, 6]

第四步： 比较 3 和 2，3 更大，所以 nums1[2] = 3，i=0, k=1。
nums1 变为 [1, 3, 3, 4, 5, 6]

第五步： 比较 1 和 2，2 更大，所以 nums1[1] = 2，j=-1, k=0。
nums1 变为 [1, 2, 3, 4, 5, 6]

第六步： j < 0，说明 nums2 已处理完。nums1 中剩余的元素（i=0）已经在正确位置，无需移动。最终结果为 [1, 2, 3, 4, 5, 6]。

代码实现（Python示例）

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, 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
    # nums1 剩余元素已在正确位置，无需处理

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

• 时间复杂度： O(m + n)。因为每个元素最多被比较和移动一次。
• 空间复杂度： O(1)。除了几个指针变量外，没有使用额外数组。

为什么这种方法可行（正确性证明）

循环不变式（关键思想）：
在每次迭代开始时，nums1[k+1:]（即 nums1 中从索引 k+1 到末尾的部分）已经是有序的，并且包含了所有从 nums1[i+1:] 和 nums2[j+1:] 中已经处理过的较大元素。同时，nums1[:i+1] 和 nums2[:j+1] 中的元素尚未被放置到最终位置，但它们都小于等于 nums1[k+1:] 中的元素。

初始状态：
k = m + n - 1，nums1[k+1:] 为空，满足有序。nums1[:m] 和 nums2[:n] 全部未处理。

保持：
每次比较 nums1[i] 和 nums2[j]，将较大者放到 nums1[k]。由于数组初始有序，且我们是从后向前放，所以新放入 nums1[k] 的元素一定是当前未处理元素中最大的，它比已经放好的 nums1[k+1:] 中的元素都小或相等（因为是从大到小放置），因此 nums1[k:] 保持有序。然后相应指针移动，不变式得以保持。

终止：

• 如果 i 先耗尽，说明 nums1 的元素全部处理完，nums2 剩余的元素都是最小的，直接依次放入 nums1 前部，nums1 整体有序。
• 如果 j 先耗尽，说明 nums2 元素全部处理完，nums1 剩余的元素已经在正确位置（它们本身就是有序的，并且小于等于已放置的元素），无需移动。

边界情况与注意事项

1. 空数组： 如果 m=0，则 i=-1，循环直接处理 nums2 全部元素即可。同理 n=0 则直接结束。
2. 所有元素相等： 算法同样正确，因为条件 nums1[i] > nums2[j] 不成立时会取 nums2[j]，保证了稳定性（如果要求稳定，这里不严格保证，但本题不要求稳定性）。
3. 原地合并： 该算法充分利用了 nums1 尾部空间，避免额外数组，是经典的双指针从后向前合并技巧。

通过这个详细的讲解，你应当能理解如何使用双指针技巧，在 O(1) 额外空间内完成两个有序数组的原地合并。这种方法不仅高效，而且在很多需要合并有序序列的场景中（如归并排序的最后一步）都有应用价值。