维基百科上关于快速排序的词条:

Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case Θ(nlogn) running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that, when operating on arrays, it requires Θ(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only Θ(logn) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.)

正如其他人所注意到的，快速排序的最坏情况是O(n²)，而归并排序和堆排序则停留在O(nlogn)。然而，在平均情况下，这三个都是O(nlogn);所以它们在大多数情况下是可比较的。

平均而言，快速排序更好的地方在于，内循环意味着将多个值与单个值进行比较，而在其他两个循环中，每次比较时两个项都是不同的。换句话说，Quicksort的读取次数是其他两种算法的一半。在现代cpu上，访问时间在很大程度上决定了性能，因此快速排序最终成为一个很好的首选。

在c/c++领域，当不使用stl容器时，我倾向于使用快速排序，因为它是构建的 进入运行时，而归并排序没有。

所以我相信，在许多情况下，这只是阻力最小的途径。

此外，对于整个数据集不适合工作集的情况，快速排序的性能可以高得多。

在归并排序中，一般算法为:

对左子数组进行排序 对右子数组进行排序 合并两个已排序的子数组

在顶层，合并两个已排序的子数组涉及处理N个元素。

再往下一层，第3步的每次迭代都涉及处理N/2个元素，但您必须重复此过程两次。所以你仍然在处理2 * N/2 == N个元素。

再往下一层，你要合并4 * N/4 == N个元素，以此类推。递归堆栈中的每个深度都涉及合并相同数量的元素，涉及对该深度的所有调用。

考虑一下快速排序算法:

选择一个枢轴点 将枢轴点放置在数组中的正确位置，所有较小的元素放在左边，较大的元素放在右边 对左子数组进行排序 对右子数组排序

在顶层，你处理的是一个大小为n的数组，然后选择一个枢轴点，把它放在正确的位置，然后可以在算法的其余部分完全忽略它。

再往下一层，您将处理2个子数组，它们的组合大小为N-1(即减去之前的枢轴点)。为每个子数组选择一个枢轴点，总共有2个额外的枢轴点。

再往下一层，您将处理4个子数组，它们的组合大小为N-3，原因与上面相同。

然后N-7…然后c15…然后N-32…

递归堆栈的深度保持大致相同(logN)。使用归并排序，你总是在递归堆栈的每一层处理n个元素的归并。但是使用快速排序，你要处理的元素数量会随着你在堆栈中向下移动而减少。例如，如果你在递归堆栈中查看深度，你正在处理的元素数量是N - 2^((logN)/2)) == N -根号(N)。

声明:对于归并排序，因为每次都将数组分割为两个完全相等的块，所以递归深度正好是logN。在快速排序时，由于枢轴点不太可能恰好位于数组的中间，因此递归堆栈的深度可能略大于logN。我还没有做过数学计算，看看这个因素和上面描述的因素在算法复杂性中究竟扮演了多大的角色。

在所有条件相同的情况下，我希望大多数人使用最方便的方法，这往往是qsort(3)。除此之外，快速排序在数组上非常快，就像归并排序是列表的常用选择一样。

我想知道的是为什么基数排序和桶排序这么少见。它们是O(n)至少在链表上是这样的它所需要的只是将键转换为序数的方法。(字符串和浮动工作得很好。)

我认为原因与计算机科学的教学方式有关。我甚至不得不向我的讲师演示算法分析，它确实有可能比O(nlog (n))更快地排序。(他证明了比较排序不能比O(nlog (n))快，这是正确的)

在其他新闻中，浮点数可以按整数排序，但之后必须将负数反转。

编辑: 实际上，这里有一种更糟糕的将浮点数作为整数排序的方法:http://www.stereopsis.com/radix.html。注意，不管你实际使用什么排序算法，比特翻转技巧都可以使用……

维基百科的解释是:

通常，快速排序在实践中比其他Θ(nlogn)算法要快得多，因为它的内部循环可以在大多数架构上有效地实现，并且在大多数现实数据中，可以做出设计选择，使需要二次时间的概率最小化。

快速排序

Mergesort

我认为归并排序(即Ω(n))所需要的存储量也存在快速排序实现所不具备的问题。在最坏的情况下，它们的算法时间是相同的，但归并排序需要更多的存储空间。