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


当前回答

在所有条件相同的情况下,我希望大多数人使用最方便的方法,这往往是qsort(3)。除此之外,快速排序在数组上非常快,就像归并排序是列表的常用选择一样。

我想知道的是为什么基数排序和桶排序这么少见。它们是O(n)至少在链表上是这样的它所需要的只是将键转换为序数的方法。(字符串和浮动工作得很好。)

我认为原因与计算机科学的教学方式有关。我甚至不得不向我的讲师演示算法分析,它确实有可能比O(nlog (n))更快地排序。(他证明了比较排序不能比O(nlog (n))快,这是正确的)

在其他新闻中,浮点数可以按整数排序,但之后必须将负数反转。

编辑: 实际上,这里有一种更糟糕的将浮点数作为整数排序的方法:http://www.stereopsis.com/radix.html。注意,不管你实际使用什么排序算法,比特翻转技巧都可以使用……

其他回答

当我试验这两种排序算法时,通过计算递归调用的次数, 快速排序始终比归并排序具有更少的递归调用。 这是因为快速排序有枢轴,而在下一个递归调用中不包括枢轴。这样快速排序可以比归并排序更快地达到递归基本情况。

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

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

快速排序是最坏情况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.

这是一个相当老的问题,但因为我最近处理了这两个问题,所以这里是我的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 —归并排序需要占用额外空间

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