我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
这是一个相当老的问题,但因为我最近处理了这两个问题,所以这里是我的2c:
归并排序平均需要~ N log N次比较。对于已经(几乎)排序过的排序数组,这可以达到1/ 2nlog N,因为在归并时,我们(几乎)总是选择“左边”的1/ 2n次,然后只复制右边1/ 2n个元素。此外,我可以推测,已经排序的输入使处理器的分支预测器发光,但猜测几乎所有的分支都正确,从而防止管道停顿。
快速排序平均需要~ 1.38 nlog N个比较。在比较方面,它不会从已经排序的数组中获得很大的好处(但是在交换方面,可能在CPU内部的分支预测方面,它会获得很大的好处)。
我在相当现代的处理器上的基准测试显示如下:
当比较函数是回调函数时(如qsort() libc实现),对于随机输入,快速排序比归并排序慢15%,对于已经排序的64位整数,快排序比归并排序慢30%。
另一方面,如果比较不是回调,我的经验是快速排序优于归并排序高达25%。
然而,如果你的(大)数组只有很少的唯一值,归并排序在任何情况下都开始超过快速排序。
因此,底线可能是:如果比较是昂贵的(例如,回调函数,比较字符串,比较结构的许多部分,主要是得到第二个,第三个,第四个“if”来产生差异)-很可能你会更好地使用归并排序。对于简单的任务,快速排序会更快。
之前所说的都是真的: -快速排序可以是N^2,但Sedgewick声称,一个好的随机实现有更多的机会,计算机执行排序被闪电击中比N^2 —归并排序需要占用额外空间
其他回答
实际上,快速排序是O(n2)。它的平均情况运行时间是O(nlog(n)),但最坏情况是O(n2),这发生在在包含很少唯一项的列表上运行时。随机化花费O(n)。当然,这并没有改变最坏的情况,它只是防止恶意用户使您的排序花费很长时间。
快速排序更受欢迎,因为它:
(MergeSort需要额外的内存,与要排序的元素数量成线性关系)。 有一个小的隐藏常数。
快速排序是在实践中最快的排序算法,但有一些病态的情况,可以使它的表现差到O(n2)。
堆排序保证在O(n*ln(n))中运行,并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。
虽然它们都在相同的复杂度类中,但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快,因为它更容易编写紧凑的实现代码,它所做的操作也更快。这是因为快速排序通常更快,人们使用它而不是归并排序。
然而!我个人经常会使用归并排序或快速排序变体,当快速排序表现不佳时,它们会降级为归并排序。记住。快速排序平均只有O(n log n)最坏情况是O(n²)归并排序总是O(n log n).在实时性能或响应性是必须的情况下,你的输入数据可能来自恶意来源,你不应该使用简单的快速排序。
答案将略微倾向于快速排序w.r.t的变化带来的DualPivotQuickSort的基本值。它在JAVA 7中用于在JAVA .util. arrays中排序
It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.
您可以在这里找到JAVA7实现- http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java
关于DualPivotQuickSort的进一步精彩阅读- http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
快速排序和合并排序的小增加。
它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作,就像比较平面内存中的整数一样,那么归并排序可能是更可取的算法。
例如,我们在远程服务器上使用网络协议对项目进行排序。
而且,在像“链表”这样的自定义容器中,也没有快速排序的好处。 1. 对链表进行归并排序,不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)