合并然后进行排序或排序然后合并会更快吗？

我有2个数组没有排序。将它们单独分类然后合并它们会更快吗？或者只是先串联数组并排序组合巨大数组会更快？合并然后进行排序或排序然后合并会更快吗？

来源

2013-04-10 Kunal Kapoor

似乎第二种方法更快，因为串联速度更快，然后合并。 – Egor 2013-04-10 11:30:13

我宁愿分而治之。快速排序和合并排序从中受益。 – 2013-04-10 11:31:55

@Egor排序是一种比串联和合并更少线性的操作（除非我们正在谈论基数排序）。 – 2013-04-10 11:33:04

很明显，大O在这个问题上并没有真正的说什么。假设你正在使用的算法是快速排序。 It has a average running time of:

enter image description here

所以，现在，如果排序然后合并，我们得到：

F1 = 1.39n *的log（n）* 2 + 2N

合并然后排序：

F2 = n + 1.39 * 2n * log（2n）

区别是

f2 -f1 = -n + 2。78N> 0

在一般情况下，如果一个排序算法具有复杂

C = K * n日志（n）的

然后由于k应该是通常大于1，并且是不太可能在0.5附近的任何地方，如果您假设合并成本最多为2n，那么合并将会更快。

来源

2013-04-10 13:42:58

我认为用这种方法分析算法的运行时间并不是很有意义。大O符号忽略的实际常量的使用表明它更加准确，但您仍然只计算选定的操作（比较次数，复制次数）并忽略其他许多操作（方法调用，缓存效果等）。国际海事组织（IMO），如果你想执行比big-O更接近实际的分析，你还应该考虑所有系统/语言/实现特定的常量，并使用分析器来代替。 – blubb 2013-04-11 08:59:21

@blubb你绝对是对的;我忘了在我的回答中提到，这只是比较输入随机时的平均比较次数。上述分析必须扩展，并定义计算模型。我会尽量编辑答案，使其更加真实世界，而不是在稍后的某一段时间只是一个粗俗的废话。 – 2013-04-11 11:28:43

我认为这将取决于排序算法和数据的大小。

但一个疯狂的猜测是合并，然后排序整个批次是可取的。因为在这种情况下的合并只是追加。

而在另一种情况下，您将需要应用排序合并。

来源

2013-04-10 11:32:24

尽管您的答案可能会更简单，但问题的要求并不会更快。 – Alan 2013-04-10 11:38:14

我认为在具体代码运行之前没有确定的答案。 – 2013-04-10 11:54:15

如果确保第二个数组中的所有条目都大于第一个数组中的所有条目，那么可以在对每个数组进行排序后连接数组。每种排序算法的复杂性都比线性更差，所以当您可以将排序任务分解为可以单独排序的子集时，应该这样做。

但是当条目在合并数组之后需要重新排序时，事先对每个数组进行排序不可能使其更快。

如果您想准确知道它，请创建一大组测试数据并自行测量性能。

来源

2013-04-10 11:34:21 Philipp

这取决于您使用的技术。

排序第一，然后合并会给你更好的结果在一个现代的多处理器体系结构，你可以在两个阵列上运行排序算法并行线程O(nlogn)左右（但有更少的常量），然后合并它们在O(n)时间。

来源

2013-04-10 11:35:04 Ali

假设串联在O(1)完成，合并需要O(n)和排序O(n log n)，您有以下选择：

排序和合并：O(n log n) + O(n) = O(n log n)
连击和排序：O(1) + O((2n) log (2n)) = O(n log n)

因此，两个选项渐近地相等。

当然，如果你使用使用MergeSort，那么整个讨论都是无稽之谈。

来源

2013-04-10 11:35:10 blubb

+1“整个讨论无论如何......” – 2013-04-10 11:47:19

我不认为串联将是Java中的“O（1）”。 – assylias 2013-04-10 12:14:05

@assylias：很可能。然而，只要连接不会超过'O（n log n）'操作，参数仍然有效。 – blubb 2013-04-10 12:34:55

合并然后进行排序或排序然后合并会更快吗？

回答

相关问题