在不使用额外空间的情况下合并两个已排序数组

在本教程中，我们将编写 Python 程序来合并两个已排序的数组，而无需使用额外的数组或空间。这个问题在技术面试中很常见。我们将使用各种技术来解决这个问题。让我们先理解问题陈述。

给定两个列表 arr1 和 arr2，它们都按升序排序。我们需要将它们合并成一个已排序的列表，而无需使用任何额外的存储空间。arr1 包含前 N 个元素，arr2 包含后 M 个元素。最终，arr1 和 arr2 都将是有序的。

让我们来理解解决方案。

方法 - 1：蛮力法（朴素方法）

在朴素方法中，我们反复比较和交换两个数组中的元素，将它们合并成一个已排序的列表。以下是朴素方法的 Python 实现。

示例 -

输出

arr1 after merge: [1, 2, 3, 4]
arr2 after merge: [6, 7, 8]

解释 -

上面的代码演示了一种朴素的方法，可以将两个已排序的数组 `arr1` 和 `arr2` 合并成一个已排序的数组，而无需使用任何额外的空间。以下是分步说明：

1. 我们定义一个函数 `merge_sorted_arrays_naive`，它接受四个参数：`arr1`、`arr2`（第二个已排序数组）、`n`（arr1 的长度）和 `m`（arr2 的长度）。
2. 在函数内部，我们使用嵌套循环遍历 `arr1` 中的每个元素（外层循环）和 `arr2` 中的元素（内层循环）。
3. 对于 `arr1` 中的每个元素，我们将其与 `arr2` 的第一个元素进行比较（因为两个数组都已排序）。如果 `arr1` 中的元素大于 `arr2` 的第一个元素，我们使用 Python 的元组解包功能交换它们。
4. 交换后，我们对 `arr2` 进行排序，以保持其排序顺序，因为交换元素可能会破坏顺序。
5. 我们对 `arr1` 中的每个元素重复此过程，从而有效地合并两个数组。这种方法确保合并后的 `arr1` 包含前 n 个元素，而 `arr2` 包含后 m 个元素。
6. 最后，我们返回修改后的 `arr1` 和 `arr2`。
7. 在示例用法中，我们演示了如何使用 merge_sorted_arrays_naive() 函数处理两个示例数组 arr1 和 arr2。合并后，我们打印修改后的数组。

需要注意的是，这种朴素方法并不是合并已排序数组的最有效方法，尤其对于大型数组而言，因为它涉及对 arr2 的重复排序。还有其他更有效的算法可以在不使用额外空间的情况下合并两个已排序的数组，例如基于归并排序的方法，其时间复杂度为 O(n + m)。

最优方法 - 1

此解决方案比蛮力方法更有效。让我们来理解下面的例子：

示例 -

输出

arr1 after merging: [0, 1, 2, 3]
arr2 after merging: [5, 6, 7, 8, 9]

解释 -

在上面的代码中，我们初始化了两个指针，left 和 right，其中 left 指向 arr1 的最后一个索引，right 指向 arr2 的第一个索引。

当 left 大于或等于 0 且 right 小于 m（arr2 的长度）时，我们比较这两个指针处的元素。如果 arr1[left] 大于 arr2[right]，我们交换这两个元素。否则，由于数组已排序，我们停止移动指针。

指针遍历完数组后，arr1 将包含较小的元素，arr2 将包含较大的元素。

最后，我们对 arr1 和 arr2 进行排序，以确保它们按升序排序。

时间复杂度： O(n * log(n) + m * log(m)) + O(n + m)

空间复杂度 - 0(1)，因为我们没有使用额外的空间。

最优解决方案 - 2

在此方法中，我们将使用基于希尔排序算法的 Gap 方法。这是一种有效地就地合并两个已排序数组的技术。这种方法通过减少比较和交换的次数来优化朴素方法。让我们来理解下面的例子。

示例 -

输出

arr1 after merging: [0, 1, 2, 3]
arr2 after merging: [5, 6, 7, 8, 9]

解释 -

在上面的代码中

我们通过将两个数组的长度相加并除以 2 来计算初始步长。

我们使用一个 while 循环，只要步长大于 0，循环就会继续。此循环基于步长值控制排序和合并过程。

在循环的第一部分，我们对 arr1 进行希尔排序，然后比较并交换相距步长位置的元素，直到到达 arr1 的末尾。

在第二部分，我们合并 arr1 和 arr2 之间的元素，然后比较并交换步长距离内的元素，并相应地前进指针 i 和 j。

最后，如果 arr2 中还有剩余的元素需要排序（即，如果 j 小于 m），我们对 arr2 进行希尔排序。

我们在每次迭代中将步长减半，继续排序过程，直到步长变为 0。

此实现有效地合并了两个已排序的数组，而无需使用额外的空间，并且基于源自希尔排序的 Gap 方法。此方法的​​时间复杂度优于朴素方法。

结论

在本教程中，我们学习了如何在不使用额外空间的情况下合并两个已排序的数组。我们探索了三种方法：涉及排序的朴素方法、使用指针的最优方法以及基于源自希尔排序的 Gap 技术的高效方法。最优和高效的方法最大限度地减少了不必要的交换和比较，使其更适合大型数组。通过遵循这些技术，您可以就地合并已排序的数组，使其成为技术面试和实际应用中的宝贵技能。