两个数组的原地合并

Question

我们有一个大小为m+n的数组，其中m个元素以排序顺序存在，并且第二个大小为n的数组也按排序顺序存在。我们希望将它们都排序并放置在第一个数组中，不应该给出第三个数组。

示例：

   1, 3, 55, 66, 77, _, _, _ 
   5, 9, 20 

答案应该是：

   1, 3, 5, 9, 20, 55, 66, 77 

- algo-geeks

---

那就使用归并排序。问题是什么？ - Pete Kirkham

@Mark Byers 不是重复的问题，因为这个有额外的存储空间，而不是真正的原地算法。 - Pete Kirkham

这实际上不是原地合并。这只是将第二个数组合并到第一个数组中，可以使用许多算法实现，从琐碎且愚笨的插入排序到更为复杂的算法。原地合并是一个经典问题，它意味着两个子数组最初都存储在第一个数组中。 - AnT stands with Russia

Answer 1

进行常规的归并排序，但是以相反的方式比较最大的数字，将（反转后的）结果存储到第一个数组的末尾向后倒序。这样，您合并的元素永远不会被覆盖（如果您花一点时间思考，就很容易看出这种方法的有效性）。

- user97370

---

好的回答。将你的答案中的“排序”一词删除。这会让人感到困惑。建议改为“做一个常规的归并”。 - Mangoose

谢谢，看了你的回答后，这个问题终于豁然开朗了。我一直在想为什么元素没有被覆盖，最终看到有人至少承认这可能是个问题，让我明白了它的工作原理。哈哈。 - JHS

Answer 2

    // merge the elements in B[] to A[], starting from the last one
    void merge(int A[], int m, int B[], int n) {
       // m-1 and n-1 represent the current element index in A[] and B[] respectively
      while (n > 0) { // there are still elements in B[] not merged
          if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[]
            A[m+n-1] = A[m-1]; // move current element of A[] to its right position
            --m; // decrease current element index of A[]
          }
         else { // current element in A[] <= current element in B[]
            A[m+n-1] = B[n-1]; // move current element in B[] to its right position
            --n; // decrease current element index of B[]
         }
      }
   }

- Yanling

---

你能提供一些解释吗？ - Undo

Answer 3

将第一个数组的内容移动到第一个数组的末尾，使得空元素现在位于开头。然后像往常一样将两个序列合并到第一个数组中。

- Markus Kull

---

为什么需要将元素移动到第一个数组的末尾？我们可以从两个数组的末尾开始比较元素，并将它们放置在第一个数组的末尾。 - algo-geeks

@prp 你的建议也应该可行，而且可能更容易。我只是习惯了通过选择较小的来合并。 - Markus Kull

Answer 4

“就地”基本上要求我们只使用“常量”数量的内存，这个数量不会随着不同输入数组大小而改变。然而，问题本身分配了额外的内存量，这个量与两个输入数组中的一个的大小相同，在最坏情况下是O(n)内存。这基本上使“就地”这个想法毫无意义...

问题的表述可能更好地为“在没有额外内存的情况下合并”，这更准确地描述了它的真实意图...

- Yaxiong Zhao