我在一次面试中被问到这个问题。它们都是O(nlogn),但大多数人使用快速排序而不是归并排序。为什么呢?
当前回答
快速排序具有更好的平均情况复杂度,但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入,他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。
归并排序的平均情况复杂性和最坏情况复杂性是相同的,因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说,因为没有导致它运行得非常非常慢的病理情况。
由于这些原因,我更喜欢归并排序,而不是快速排序。
其他回答
快速排序具有更好的平均情况复杂度,但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入,他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。
归并排序的平均情况复杂性和最坏情况复杂性是相同的,因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说,因为没有导致它运行得非常非常慢的病理情况。
由于这些原因,我更喜欢归并排序,而不是快速排序。
快速排序是在实践中最快的排序算法,但有一些病态的情况,可以使它的表现差到O(n2)。
堆排序保证在O(n*ln(n))中运行,并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。
快速排序并不比归并排序好。对于O(n²)(很少发生的最坏情况),快速排序可能比归并排序的O(nlogn)慢得多。快速排序的开销更小,所以对于小n和速度较慢的计算机,它会更好。但是今天的计算机是如此之快,以至于合并排序的额外开销可以忽略不计,并且在大多数情况下,非常慢的快速排序的风险远远超过合并排序的微不足道的开销。
此外,归并排序将具有相同键的项按原始顺序保留,这是一个有用的属性。
我想补充的是,到目前为止提到的三种算法(归并排序,快速排序和堆排序)只有归并排序是稳定的。也就是说,对于那些具有相同键的值,顺序不会改变。在某些情况下,这是可取的。
但是,说实话,在实际情况下,大多数人只需要良好的平均性能和快速排序…快速=)
所有排序算法都有其起伏。有关排序算法的概述,请参阅维基百科的文章。
维基百科的解释是:
通常,快速排序在实践中比其他Θ(nlogn)算法要快得多,因为它的内部循环可以在大多数架构上有效地实现,并且在大多数现实数据中,可以做出设计选择,使需要二次时间的概率最小化。
快速排序
Mergesort
我认为归并排序(即Ω(n))所需要的存储量也存在快速排序实现所不具备的问题。在最坏的情况下,它们的算法时间是相同的,但归并排序需要更多的存储空间。