我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
快速排序是在实践中最快的排序算法,但有一些病态的情况,可以使它的表现差到O(n2)。
堆排序保证在O(n*ln(n))中运行,并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。
其他回答
但大多数人使用快速排序而不是归并排序。为什么呢?”
一个没有给出的心理学原因是,快速排序的名字更为巧妙。很好的市场营销。
是的,带有三重分区的快速排序可能是最好的通用排序算法之一,但“快速”排序听起来比“归并”排序强大得多,这是无法克服的事实。
当我试验这两种排序算法时,通过计算递归调用的次数, 快速排序始终比归并排序具有更少的递归调用。 这是因为快速排序有枢轴,而在下一个递归调用中不包括枢轴。这样快速排序可以比归并排序更快地达到递归基本情况。
正如许多人所注意到的,快速排序的平均情况性能要比归并排序快。但这只适用于假设按需访问任何内存段的时间为常数的情况。
在RAM中,这种假设通常不太坏(由于缓存的存在,这种假设并不总是正确的,但也不太坏)。然而,如果你的数据结构足够大,可以存储在磁盘上,那么快速排序就会因为磁盘平均每秒进行200次随机查找而被扼杀。但是,同样的磁盘在按顺序每秒读取或写入兆字节的数据方面没有任何问题。这正是归并排序所做的。
因此,如果数据必须在磁盘上排序,你真的,真的想使用归并排序的一些变体。(通常你快速排序子列表,然后开始将它们合并到某个大小阈值以上。)
Furthermore if you have to do anything with datasets of that size, think hard about how to avoid seeks to disk. For instance this is why it is standard advice that you drop indexes before doing large data loads in databases, and then rebuild the index later. Maintaining the index during the load means constantly seeking to disk. By contrast if you drop the indexes, then the database can rebuild the index by first sorting the information to be dealt with (using a mergesort of course!) and then loading it into a BTREE datastructure for the index. (BTREEs are naturally kept in order, so you can load one from a sorted dataset with few seeks to disk.)
在许多情况下,了解如何避免磁盘寻道使我将数据处理工作花费数小时而不是数天或数周。
这是一个相当老的问题,但因为我最近处理了这两个问题,所以这里是我的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 —归并排序需要占用额外空间
在所有条件相同的情况下,我希望大多数人使用最方便的方法,这往往是qsort(3)。除此之外,快速排序在数组上非常快,就像归并排序是列表的常用选择一样。
我想知道的是为什么基数排序和桶排序这么少见。它们是O(n)至少在链表上是这样的它所需要的只是将键转换为序数的方法。(字符串和浮动工作得很好。)
我认为原因与计算机科学的教学方式有关。我甚至不得不向我的讲师演示算法分析,它确实有可能比O(nlog (n))更快地排序。(他证明了比较排序不能比O(nlog (n))快,这是正确的)
在其他新闻中,浮点数可以按整数排序,但之后必须将负数反转。
编辑: 实际上,这里有一种更糟糕的将浮点数作为整数排序的方法:http://www.stereopsis.com/radix.html。注意,不管你实际使用什么排序算法,比特翻转技巧都可以使用……