快速排序是在实践中最快的排序算法，但有一些病态的情况，可以使它的表现差到O(n2)。

堆排序保证在O(n*ln(n))中运行，并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。

我想补充的是，到目前为止提到的三种算法(归并排序，快速排序和堆排序)只有归并排序是稳定的。也就是说，对于那些具有相同键的值，顺序不会改变。在某些情况下，这是可取的。

但是，说实话，在实际情况下，大多数人只需要良好的平均性能和快速排序…快速=)

所有排序算法都有其起伏。有关排序算法的概述，请参阅维基百科的文章。

这是采访中经常被问到的一个问题，尽管归并排序在最坏情况下性能更好，但快速排序被认为比归并排序更好，特别是对于大输入。以下是快速排序更好的原因:

1-辅助空间:快速排序是一种就地排序算法。就地排序意味着执行排序不需要额外的存储空间。另一方面，归并排序需要一个临时数组来归并已排序的数组，因此它并不到位。

2-最坏情况:快速排序O(n^2)的最坏情况可以通过使用随机化快速排序来避免。通过选择正确的枢轴，可以很容易地避免这种情况。通过选择合适的枢轴元来获得平均情况下的行为，从而提高了算法的性能，达到了与归并排序一样的效率。

3-引用的局部性:快速排序特别展示了良好的缓存局部性，这使得它在许多情况下比归并排序更快，比如在虚拟内存环境中。

4-尾递归:快速排序是尾递归，而归并排序不是。尾递归函数是一种函数，其中递归调用是函数执行的最后一件事。尾递归函数被认为比非尾递归函数更好，因为尾递归可以被编译器优化。

实际上，快速排序是O(n2)。它的平均情况运行时间是O(nlog(n))，但最坏情况是O(n2)，这发生在在包含很少唯一项的列表上运行时。随机化花费O(n)。当然，这并没有改变最坏的情况，它只是防止恶意用户使您的排序花费很长时间。

快速排序更受欢迎，因为它:

(MergeSort需要额外的内存，与要排序的元素数量成线性关系)。 有一个小的隐藏常数。

亩! 快速排序并不比归并排序更好，它非常适合于不同类型的应用。

归并排序是值得考虑的，如果速度是本质，糟糕的最差情况性能不能容忍，并且有额外的空间可用

你说他们«他们都是O(nlogn)[…]»。这是错误的。«快速排序使用大约n^2/2比较在最坏的情况下。

然而，根据我的经验，最重要的属性是在使用带有命令式范式的编程语言进行排序时，可以轻松实现顺序访问。

1 Sedgewick，算法

快速排序是在实践中最快的排序算法，但有一些病态的情况，可以使它的表现差到O(n2)。

堆排序保证在O(n*ln(n))中运行，并且只需要有限的额外存储空间。但是有许多真实世界的测试表明堆排序比快速排序平均要慢得多。