我在接受采访时被问到这个问题.他们都是O(nlogn),但大多数人使用Quicksort而不是Mergesort.这是为什么？
正如许多人所指出的,快速排序的平均案例性能比mergesort快. 但是,如果您假设有时间按需访问任何内存,则情况才是正确的.
在RAM中,这个假设通常不是太糟糕(因为缓存并不总是如此,但它并不太糟糕).但是,如果您的数据结构足够大,可以存放在磁盘上,那么快速排序会因为您的平均磁盘每秒执行200次随机搜索而被杀死.但是同一个磁盘在顺序读取或写入每秒兆字节的数据方面没有问题.这正是mergesort的作用.
因此,如果必须在磁盘上对数据进行排序,那么您真的非常希望在mergesort上使用一些变体.(通常,您会快速排序子列表,然后开始将它们合并到一些大小阈值之上.)
此外,如果您必须对该大小的数据集执行任何操作,请仔细考虑如何避免寻找磁盘.例如,这就是为什么在数据库中执行大量数据加载之前删除索引的标准建议,然后再重建索引.在加载期间维护索引意味着不断寻求磁盘.相比之下,如果删除索引,那么数据库可以通过首先对要处理的信息进行排序(当然使用mergesort!)然后将其加载到索引的BTREE数据结构中来重建索引.(BTREE自然是按顺序保存的,因此您可以从排序的数据集中加载一个,只需很少的搜索到磁盘.)
在很多情况下,理解如何避免磁盘搜索让我使数据处理工作需要数小时而不是数天或数周.
Quicksort具有O(n 2)最坏情况运行时和O(n log n)平均情况运行时.但是,它在许多场景中优于合并排序,因为许多因素会影响算法的运行时间,并且当将它们全部放在一起时,快速排序会胜出.
特别地,经常引用的排序算法运行时指的是执行排序数据所需的比较次数或交换次数.这确实是衡量性能的一个很好的指标,特别是因为它独立于底层硬件设计.但是,其他的东西 - 比如引用的位置(即我们读了很多可能在缓存中的元素？) - 在当前的硬件上也扮演着重要的角色.Quicksort特别需要很少的额外空间并且具有良好的缓存局部性,这使得它在许多情况下比合并排序更快.
此外,通过使用适当的枢轴选择 - 例如随机选择它(这是一个很好的策略),很容易避免快速排序的O(n 2)的最坏情况运行时间.
在实践中,许多现代的quicksort实现(特别是libstdc ++ std::sort)实际上都是introsort,其理论最坏情况是O(n log n),与merge sort相同.它通过限制递归深度来实现这一点,并且一旦超过log n就切换到不同的算法(heapsort).
实际上,QuickSort是O(n 2).它的平均案例运行时间是O(nlog(n)),但最坏的情况是O(n 2),当你在包含很少的唯一项目的列表上运行它时会发生.随机化需要O(n).当然,这并没有改变它最糟糕的情况,它只是防止恶意用户花费很长时间进行排序.
QuickSort更受欢迎,因为它:
就地(MergeSort需要额外的内存线性到要排序的元素数量).
有一个小的隐藏常数.
"然而大多数人使用Quicksort而不是Mergesort.为什么会这样？"
没有给出的一个心理原因就是Quicksort更加巧妙地命名.即良好的营销.
是的,具有三重分区的Quicksort可能是最好的通用排序算法之一,但是没有克服"快速"排序听起来比"合并"排序更强大的事实.
正如其他人所说,Quicksort的最坏情况是O(n ^ 2),而mergesort和heapsort留在O(nlogn).然而,在一般情况下,所有三个都是O(nlogn); 所以他们对绝大多数情况都具有可比性.
使Quicksort平均更好的原因是内循环意味着将几个值与单个值进行比较,而另外两个值对于每个比较都是不同的.换句话说,Quicksort读取的数量是其他两种算法的一半.在现代CPU上,性能主要受访问时间的影响,因此最终Quicksort成为首选.
我想补充到目前为止提到的三个算法(mergesort,quicksort和heap sort),只有mergesort是稳定的.也就是说,对于具有相同键的那些值,顺序不会改变.在某些情况下,这是可取的.
但是,说实话,在实际情况下,大多数人只需要良好的平均表现,快速排序就是......快=)
所有排序算法都有其起伏.有关排序算法的信息,请参阅Wikipedia文章以获得良好的概
来自维基百科的Quicksort条目:
Quicksort还与mergesort竞争,这是另一种递归排序算法,但具有最坏情况Θ(nlogn)运行时间的好处.Mergesort是一种稳定的类型,与quicksort和heapsort不同,可以很容易地适应在链接列表和存储在缓慢访问介质(如磁盘存储或网络附加存储)上的非常大的列表上运行.尽管可以编写快速排序以在链接列表上操作,但是它通常会在没有随机访问的情况下遭受不良的数据透视选择.mergesort的主要缺点是,当在数组上操作时,它在最佳情况下需要Θ(n)辅助空间,而具有就地分区和尾递归的快速排序的变体仅使用Θ(logn)空间.(请注意,在链接列表上操作时,mergesort只需要一小块恒定的辅助存储空间.)
亩! Quicksort并不是更好,它比mergesort更适合不同类型的应用程序.
如果速度至关重要,Mergesort是值得考虑的,不能容忍坏的最坏情况,并且可以获得额外的空间.1
你说他们"他们都是O(nlogn)[...]».这是错的.«Quicksort在最坏的情况下使用大约n ^ 2/2比较.» 1.
然而,根据我的经验,最重要的属性是在使用具有命令式范例的编程语言时,可以在排序时轻松实现顺序访问.
1 Sedgewick,算法
Quicksort是实践中最快的排序算法,但有许多病理案例可以使它的表现与O(n2)一样糟糕.
保证Heapsort在O(n*ln(n))中运行,并且只需要有限的额外存储空间.但是现实世界测试有许多引用表明,heapsort平均比快速排序明显慢.
维基百科的解释是:
通常,快速排序在实践中比其他Θ(nlogn)算法快得多,因为它的内循环可以在大多数架构上有效地实现,并且在大多数现实世界数据中,可以做出设计选择,从而最小化需要二次时间的概率. .
快速排序
归并
我认为快速排序实现所没有的Mergesort所需的存储量(即Ω(n))也存在问题.在最坏的情况下,它们的算法时间相同,但mergesort需要更多的存储空间.
京公网安备 11010802040832号 | 京ICP备19059560号-6 