我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
当我试验这两种排序算法时,通过计算递归调用的次数, 快速排序始终比归并排序具有更少的递归调用。 这是因为快速排序有枢轴,而在下一个递归调用中不包括枢轴。这样快速排序可以比归并排序更快地达到递归基本情况。
其他回答
我想补充的是,到目前为止提到的三种算法(归并排序,快速排序和堆排序)只有归并排序是稳定的。也就是说,对于那些具有相同键的值,顺序不会改变。在某些情况下,这是可取的。
但是,说实话,在实际情况下,大多数人只需要良好的平均性能和快速排序…快速=)
所有排序算法都有其起伏。有关排序算法的概述,请参阅维基百科的文章。
维基百科的解释是:
通常,快速排序在实践中比其他Θ(nlogn)算法要快得多,因为它的内部循环可以在大多数架构上有效地实现,并且在大多数现实数据中,可以做出设计选择,使需要二次时间的概率最小化。
快速排序
Mergesort
我认为归并排序(即Ω(n))所需要的存储量也存在快速排序实现所不具备的问题。在最坏的情况下,它们的算法时间是相同的,但归并排序需要更多的存储空间。
快速排序具有更好的平均情况复杂度,但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入,他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。
归并排序的平均情况复杂性和最坏情况复杂性是相同的,因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说,因为没有导致它运行得非常非常慢的病理情况。
由于这些原因,我更喜欢归并排序,而不是快速排序。
虽然它们都在相同的复杂度类中,但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快,因为它更容易编写紧凑的实现代码,它所做的操作也更快。这是因为快速排序通常更快,人们使用它而不是归并排序。
然而!我个人经常会使用归并排序或快速排序变体,当快速排序表现不佳时,它们会降级为归并排序。记住。快速排序平均只有O(n log n)最坏情况是O(n²)归并排序总是O(n log n).在实时性能或响应性是必须的情况下,你的输入数据可能来自恶意来源,你不应该使用简单的快速排序。
但大多数人使用快速排序而不是归并排序。为什么呢?”
一个没有给出的心理学原因是,快速排序的名字更为巧妙。很好的市场营销。
是的,带有三重分区的快速排序可能是最好的通用排序算法之一,但“快速”排序听起来比“归并”排序强大得多,这是无法克服的事实。