我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?


当前回答

正如其他人所注意到的,快速排序的最坏情况是O(n²),而归并排序和堆排序则停留在O(nlogn)。然而,在平均情况下,这三个都是O(nlogn);所以它们在大多数情况下是可比较的。

平均而言,快速排序更好的地方在于,内循环意味着将多个值与单个值进行比较,而在其他两个循环中,每次比较时两个项都是不同的。换句话说,Quicksort的读取次数是其他两种算法的一半。在现代cpu上,访问时间在很大程度上决定了性能,因此快速排序最终成为一个很好的首选。

其他回答

正如其他人所注意到的,快速排序的最坏情况是O(n²),而归并排序和堆排序则停留在O(nlogn)。然而,在平均情况下,这三个都是O(nlogn);所以它们在大多数情况下是可比较的。

平均而言,快速排序更好的地方在于,内循环意味着将多个值与单个值进行比较,而在其他两个循环中,每次比较时两个项都是不同的。换句话说,Quicksort的读取次数是其他两种算法的一半。在现代cpu上,访问时间在很大程度上决定了性能,因此快速排序最终成为一个很好的首选。

答案将略微倾向于快速排序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

维基百科的解释是:

通常,快速排序在实践中比其他Θ(nlogn)算法要快得多,因为它的内部循环可以在大多数架构上有效地实现,并且在大多数现实数据中,可以做出设计选择,使需要二次时间的概率最小化。

快速排序

Mergesort

我认为归并排序(即Ω(n))所需要的存储量也存在快速排序实现所不具备的问题。在最坏的情况下,它们的算法时间是相同的,但归并排序需要更多的存储空间。

快速排序和合并排序的小增加。

它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作,就像比较平面内存中的整数一样,那么归并排序可能是更可取的算法。

例如,我们在远程服务器上使用网络协议对项目进行排序。

而且,在像“链表”这样的自定义容器中,也没有快速排序的好处。 1. 对链表进行归并排序,不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)

同时考虑时间和空间的复杂性。 归并排序: 时间复杂度:O(nlogn), 空间复杂度:O(nlogn)

快速排序: 时间复杂度:O(n²), 空间复杂度:O(n)

现在,他们各自在一个场景中获胜。 但是,使用随机枢轴,您几乎总是可以将快速排序的时间复杂度降低到O(nlogn)。

因此,在许多应用中,快速排序是首选,而不是归并排序。