c# - 算法方法建议 - 按顺序合并两个数组

Question

我在一次与 C# 相关的采访中被问到这个问题。有 2 个数组 - 从最低到最高预先排序。我需要将所有这些组合在第三个数组中，并且它们应该以排序方式插入（因为它们正在进入）。

我提到的解决方案如下：

1. 为了论证起见，假设Array 1具有以下元素 -1,2,3,4,5并且Array 2具有以下元素 -6,7,8,9,10

2. 由于 2 个数组是预先排序的 - 您可以将 的第一个元素与Array 1的第一个元素进行比较Array 2，并将较低的元素插入Array 3.

3. 然后你会为Element 2ofArray 1和Element 1of做同样的事情Array 2并弹出下一个最小的数字

我提到的方法应该有效 - 但我的问题如下：

1. 这是最有效的方法吗？
2. 是否有可以描述此过程的技术术语（如二进制搜索算法等）？
3. 解决此问题的任何其他指示？

Answer 1

是的，这是最有效的方法。

它在O(n)（其中 n 是两个数组的大小）上运行，这意味着遍历数组一次。

为了创建第三个数组，无论如何您都必须遍历每个元素（即使只是以正确的顺序将其添加到第三个数组）。

这个过程通常被称为合并排序算法merge的一部分。

这是Stack Overflow 中的一个实现。

Answer 2

1) 这是最有效的方法，O(n+m)。其中 n - 第一个数组的大小，m - 第二个数组的大小。2) 称为归并排序算法的归并程序。

实际上你可以合并超过 2 个数组，通常它用于外部排序或者当你有空间限制时。

Answer 3

1. 如果您知道输入数组已排序，则合并算法将是线性的（大 O 表示法中的 O(n)）。但是，如果您还知道其中一个数组的最大值低于另一个数组的最小值，则可以使用Array.Copy而不是比较单个元素以获得更好的性能。

2. 是的，这是一个合并算法。

3. 熟能生巧。我喜欢为了好玩而解决Project Euler问题——它们很“小”，但是一旦你克服了前几个问题，它们就会真正让你思考如何解决它。

   编辑天赋：