我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
但大多数人使用快速排序而不是归并排序。为什么呢?”
一个没有给出的心理学原因是,快速排序的名字更为巧妙。很好的市场营销。
是的,带有三重分区的快速排序可能是最好的通用排序算法之一,但“快速”排序听起来比“归并”排序强大得多,这是无法克服的事实。
其他回答
快速排序是在实践中最快的排序算法,但有一些病态的情况,可以使它的表现差到O(n2)。
堆排序保证在O(n*ln(n))中运行,并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。
快速排序是最坏情况O(n²),然而,平均情况始终执行归并排序。每个算法都是O(nlogn),但你需要记住,当谈论大O时,我们忽略了较低的复杂度因素。当涉及到常数因子时,快速排序比归并排序有显著的改进。
归并排序也需要O(2n)内存,而快速排序可以就地完成(只需要O(n))。这是快速排序通常比归并排序更受欢迎的另一个原因。
额外信息:
快速排序的最坏情况发生在枢轴选择不佳时。考虑下面的例子:
[5, 4, 3, 2, 1]
If the pivot is chosen as the smallest or largest number in the group then quick sort will run in O(n^2). The probability of choosing the element that is in the largest or smallest 25% of the list is 0.5. That gives the algorithm a 0.5 chance of being a good pivot. If we employ a typical pivot choosing algorithm (say choosing a random element), we have 0.5 chance of choosing a good pivot for every choice of a pivot. For collections of a large size the probability of always choosing a poor pivot is 0.5 * n. Based on this probability quick sort is efficient for the average (and typical) case.
答案将略微倾向于快速排序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
在c/c++领域,当不使用stl容器时,我倾向于使用快速排序,因为它是构建的 进入运行时,而归并排序没有。
所以我相信,在许多情况下,这只是阻力最小的途径。
此外,对于整个数据集不适合工作集的情况,快速排序的性能可以高得多。
维基百科的解释是:
通常,快速排序在实践中比其他Θ(nlogn)算法要快得多,因为它的内部循环可以在大多数架构上有效地实现,并且在大多数现实数据中,可以做出设计选择,使需要二次时间的概率最小化。
快速排序
Mergesort
我认为归并排序(即Ω(n))所需要的存储量也存在快速排序实现所不具备的问题。在最坏的情况下,它们的算法时间是相同的,但归并排序需要更多的存储空间。