为什么快速排序比归并排序更好？

快速排序是实践中最快的排序算法，但有一些病态情况会使其表现得像O(n2)一样差。
堆排序保证在O(n*ln(n))内运行，并且仅需要有限的额外存储空间。但是有很多真实世界测试的引用表明，平均而言堆排序比快速排序慢得多。

快速排序并不比归并排序更好。快速排序的最坏情况复杂度为O(n^2)，可能比归并排序的O(nlogn)慢得多。快速排序的开销较小，因此在n较小且计算机速度较慢时，它更好。但是现在的计算机速度非常快，归并排序的额外开销可以忽略不计，而快速排序非常慢的风险远远超过了归并排序的微不足道的开销。
此外，归并排序可以保留具有相同键的项目的原始顺序，这是一个有用的属性。

维基百科的解释是：

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

快速排序

归并排序

我认为归并排序所需的存储量也存在问题（即Ω(n)），而快速排序实现则没有这个问题。在最坏情况下，它们的算法时间相同，但归并排序需要更多的存储空间。

这是一个相当古老的问题，但由于我最近都在处理这两个算法，所以我想发表一下我的看法：
归并排序平均需要 ~ N log N 次比较。对于已经（几乎）排序好的数组，这个数字会降到 1/2 N log N，因为在合并时我们（几乎）总是选择左边的一半 N 次，然后只复制右边的另一半 N 个元素。此外，我可以猜测，已经排序好的输入会使处理器的分支预测器发挥作用，几乎总是正确地猜测所有分支，从而防止管道停顿。
快速排序平均需要 ~ 1.38 N log N 次比较。它在比较方面并没有从已排序的数组中获得很大的好处（但在交换和可能在 CPU 内部的分支预测方面确实有好处）。
我在一台相当现代的处理器上进行了基准测试，结果如下：
当比较函数是回调函数（例如在 qsort() libc 实现中）时，对于 64 位整数，快速排序在随机输入上比归并排序慢 15%，在已排序数组上比归并排序慢 30%。
另一方面，如果比较不是回调，则我的经验是，快速排序比归并排序快高达 25%。
但是，如果您（大）数组中的非常少数唯一值，则无论如何，归并排序都会开始超过快速排序。
因此，也许底线是：如果比较很昂贵（例如回调函数、比较字符串、比较结构的许多部分，主要是到第二个-第三个-第四个“if”才能产生差异），那么您最好使用归并排序。对于更简单的任务，快速排序会更快。
话虽如此，之前所说的所有内容都是正确的： - 快速排序可能是 N^2，但 Sedgewick 声称一个良好的随机化实现被电脑执行排序的机会比遭受闪电打击还要小 - 归并排序需要额外的空间。

与归并排序不同，快速排序不使用辅助空间。而归并排序使用的辅助空间为O(n)。 但是，归并排序的最坏时间复杂度为O(nlogn)，而快速排序的最坏情况复杂度为O(n^2)，当数组已经排序时会发生。

为什么快速排序很好？

• 在最坏情况下，即数据已排序时，快速排序的时间复杂度为N^2，平均情况下为NlogN。可以通过在排序开始前进行随机洗牌来缓解这种情况。
• 快速排序不需要像归并排序一样占用额外的内存。
• 如果数据集很大且存在相同的项，则使用三路划分可以减少快速排序的复杂度。相同的项越多，排序效果越好。如果所有项都相同，则可以在线性时间内完成排序。（这是大多数库的默认实现）

快速排序总是比归并排序更好吗？

并非如此。

• 归并排序是稳定的，但快速排序不是。因此，如果您需要输出的结果是稳定的，您应该使用归并排序。在许多实际应用中，稳定性是必需的。
• 现在内存很便宜。因此，如果归并排序使用的额外内存对您的应用程序不重要，则使用归并排序没有任何问题。

注意：在Java中，Arrays.sort()函数对于基本数据类型使用快速排序，对于对象数据类型使用归并排序。因为对象会占用内存开销，所以对于性能而言，为归并排序增加一点点额外的开销可能没有问题。

参考资料：观看Coursera普林斯顿算法课程第三周的快速排序视频

就原始值而言，随着DualPivotQuickSort的改进，答案会稍微倾向于快速排序。在JAVA 7中，它被用于在java.util.Arrays中进行排序。

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

您可以在此找到JAVA7的实现-http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java 另外关于DualPivotQuickSort，您可以阅读以下文章 - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

在归并排序中，通用算法如下：

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

在最高层级上，将两个已排序的子数组合并涉及到处理N个元素。
在此之下的每一级别的第3步迭代都涉及处理N/2个元素，但是您必须重复这个过程两次。因此，您仍然要处理2 * N/2 == N个元素。
在此之下的一级，您正在合并4 * N/4 == N个元素，以此类推。递归堆栈中的每个深度都涉及合并相同数量的元素，跨所有该深度的调用。
相反，考虑快速排序算法：

1. 选择一个枢轴点
2. 将枢轴点放置在数组中的正确位置，使所有较小的元素位于左侧，较大的元素位于右侧
3. 对左子数组进行排序
4. 对右子数组进行排序

在最高层级上，您正在处理大小为N的数组。然后选择一个枢轴点，将其放置在正确的位置，并且可以完全忽略它在算法的其余部分中。
在此之下的一级，您正在处理两个子数组，它们的组合大小为N-1（即，减去先前的枢轴点）。您为每个子数组选择一个枢轴点，这将增加2个额外的枢轴点。
在此之下的一级，您正在处理4个子数组，其组合大小为N-3，原因与上述相同。
然后是N-7... N-15... N-32...
您的递归堆栈深度保持大致相同（logN）。对于归并排序，您始终在处理N元素合并，跨越递归堆栈的每个级别。但是，对于快速排序，随着向下移动堆栈，您处理的元素数量会减少。例如，如果查看递归堆栈中间的深度，则您正在处理的元素数为N - 2 ^ ((logN)/2)) == N - sqrt(N)。
免责声明：在归并排序中，因为每次将数组分成两个完全相等的块，递归深度正好为logN。但是，在快速排序中，由于您的枢轴点不太可能恰好位于数组的中心，因此您的递归堆栈的深度可能略大于logN。我还没有进行计算，以确定该因素和上述因素实际上在算法的复杂性中扮演了多大的角色。

快速排序的最坏情况是O(n^2)，但平均情况下表现比归并排序更好。每个算法都是O(nlogn)，但需要记住在谈论大O时，我们省略较低复杂度因素。当涉及到常数因子时，快速排序在改进方面比归并排序有显著优势。
归并排序还需要O(2n)的内存，而快速排序可以就地完成（仅需要O(n)）。这也是快速排序通常优于归并排序的另一个原因。
额外信息： 快速排序的最坏情况发生在选择枢轴不当的情况下。考虑以下示例：[5, 4, 3, 2, 1]。如果将枢轴选择为组中最小或最大的数字，则快速排序将以O(n^2)运行。选择在列表最大或最小25%中的元素的概率为0.5。对于每个枢轴的选择，该算法都有50%的机会成为良好的枢轴。对于大型集合，总是选择不良枢轴的概率为0.5*n。基于此概率，快速排序对于平均（和典型）情况是高效的。

当我尝试使用这两种排序算法并计算递归调用次数时，快速排序比归并排序始终具有更少的递归调用次数。这是因为快速排序有枢轴点，而枢轴点不包含在下一个递归调用中。这样，快速排序可以更快地达到递归基本情况，而不像归并排序那样需要更多的递归调用。