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

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

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

但大多数人使用快速排序而不是归并排序。为什么呢?”

一个没有给出的心理学原因是，快速排序的名字更为巧妙。很好的市场营销。

是的，带有三重分区的快速排序可能是最好的通用排序算法之一，但“快速”排序听起来比“归并”排序强大得多，这是无法克服的事实。

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

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

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

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

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.)

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

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

在顶层，合并两个已排序的子数组涉及处理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。我还没有做过数学计算，看看这个因素和上面描述的因素在算法复杂性中究竟扮演了多大的角色。

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

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

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