就地两个数组合并 [英] In-place merge of two arrays

问题描述

我们有大小的数组的 M + N 的，其中的 M 的元素 present，排序顺序排列和大小的第二阵列的 N 的，又是在排序顺序。我们 希望他们都来进行分类和present第一个数组中开始。没有第三组是 应该考虑。

We have an array of size m+n in which m elements are present, in sorted order, and a second array of size n, again in sorted order. We want both of them to be sorted and present in the first array. No third array is supposed to be given.

例如：

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

答案是：

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

推荐答案

执行定期合并排序但以相反的第一比较最大数字，存储（逆转）转换成第一阵列倒退的末端。这样一来，你归并元素是永远不会被覆盖（即这个工程很容易看到，如果你想想看一会儿）。

Do a regular merge sort but in reverse comparing the largest numbers first, storing (reversed) into the end of the first array going backwards. This way, the elements you're merging are never overwritten (that this works is easy to see if you think about it for a moment).

这篇关于就地两个数组合并的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！