algorithm - 两个数组的就地合并

Question

我们有一个大小为 m+n 的数组，其中有 m 个元素按排序顺序显示，第二个大小为 n 的数组也按排序顺序显示。我们希望它们都被排序并出现在第一个数组中。没有第三个数组应该给的。

例子:

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

答案是:

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

Answer 1

进行常规合并排序，但首先反向比较最大的数字，将(反向)存储到第一个数组的末尾，向后移动。这样，您要合并的元素永远不会被覆盖(如果您稍加思考，就很容易看出这是有效的)。