我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
维基百科的解释是:
通常,快速排序在实践中比其他Θ(nlogn)算法要快得多,因为它的内部循环可以在大多数架构上有效地实现,并且在大多数现实数据中,可以做出设计选择,使需要二次时间的概率最小化。
快速排序
Mergesort
我认为归并排序(即Ω(n))所需要的存储量也存在快速排序实现所不具备的问题。在最坏的情况下,它们的算法时间是相同的,但归并排序需要更多的存储空间。
其他回答
快速排序是在实践中最快的排序算法,但有一些病态的情况,可以使它的表现差到O(n2)。
堆排序保证在O(n*ln(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
快速排序是一种就地排序算法,因此它更适合于数组。另一方面,归并排序需要额外的O(N)存储空间,更适合于链表。
与数组不同,在喜欢列表中,我们可以在中间插入O(1)空间和O(1)时间的项,因此归并排序中的归并操作可以在不需要任何额外空间的情况下实现。但是,为数组分配和取消分配额外空间会对归并排序的运行时间产生不利影响。归并排序也有利于链表,因为数据是按顺序访问的,没有太多的随机内存访问。
另一方面,快速排序需要大量的随机内存访问,而使用数组,我们可以直接访问内存,而不需要像链表那样进行任何遍历。同样,快速排序用于数组时具有良好的引用局部性,因为数组连续存储在内存中。
尽管这两种排序算法的平均复杂度都是O(NlogN),但通常人们在执行普通任务时使用数组进行存储,因此快速排序应该是首选算法。
编辑:我刚刚发现归并排序最差/最好/平均情况总是nlogn,但快速排序可以从n2(最坏的情况下,元素已经排序)到nlogn(平均/最佳情况下,pivot总是将数组分为两半)。
虽然它们都在相同的复杂度类中,但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快,因为它更容易编写紧凑的实现代码,它所做的操作也更快。这是因为快速排序通常更快,人们使用它而不是归并排序。
然而!我个人经常会使用归并排序或快速排序变体,当快速排序表现不佳时,它们会降级为归并排序。记住。快速排序平均只有O(n log n)最坏情况是O(n²)归并排序总是O(n log n).在实时性能或响应性是必须的情况下,你的输入数据可能来自恶意来源,你不应该使用简单的快速排序。
实际上,快速排序是O(n2)。它的平均情况运行时间是O(nlog(n)),但最坏情况是O(n2),这发生在在包含很少唯一项的列表上运行时。随机化花费O(n)。当然,这并没有改变最坏的情况,它只是防止恶意用户使您的排序花费很长时间。
快速排序更受欢迎,因为它:
(MergeSort需要额外的内存,与要排序的元素数量成线性关系)。 有一个小的隐藏常数。