arrays - 在对组合数组进行排序时将已排序数组添加到重新分配的已排序数组的最佳方法

Question

我正试图找出针对这个特定问题的最佳解决方案。

这是我正在尝试做的事情的概要:

• 我有两个数组，A 和 B。
• B 之前已重新分配以便为 A 中的元素腾出空间。
• A 始终是一个完全填充的数组。
• B 总是至少有一个元素。
• A 和 B 都已排序。

我想在保持数组排序的同时将 A 的元素添加到 B。

例如:

//Given:
A = [1,3,5]
B = [2,4,6, , , ]

//Desired Result:
B = [1,2,3,4,5,6]

到目前为止，我想到的最快的方法是:

• 将 A 的所有元素添加到 B，需要 O(n)。
• 对组合数组进行排序，使用类似 O(nlogn) 的合并排序。

我正在尝试找出一种比 O(nlogn) 更快的方法。

在这种情况下，空间复杂度不是问题。

Answer 1

您只需要合并排序的合并步骤。合并步骤采用两个排序数组，并在 O(n) 时间内将它们组合成一个排序数组。

您可以通过在 A 和 B 的尾部而不是头部开始合并来节省一些复制时间。这将使您可以在为 B 分配的存储中就地执行合并，而无需合并到第三个数组，然后再复制回 B。