为什么快速排序比归并排序好?

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

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

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

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

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

快速排序具有更好的平均情况复杂度，但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入，他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。

归并排序的平均情况复杂性和最坏情况复杂性是相同的，因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说，因为没有导致它运行得非常非常慢的病理情况。

由于这些原因，我更喜欢归并排序，而不是快速排序。

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

快速排序也与 归并排序，另一种递归排序 算法却带着好处 最差情况Θ(nlogn)运行时间。 归并排序是一种稳定排序 快速排序和堆排序，可以 易于适应操作的链接 列表和存储在上面的非常大的列表 访问速度较慢的媒体，如磁盘 存储或网络连接的存储。 尽管快速排序可以被写入 在链表上操作，它经常会 遭受糟糕的枢轴选择 随机存取。主要缺点 归并排序的是，操作时 对于数组，需要Θ(n)辅助 最好的情况是空格，而 就地快速排序的变体 分区和尾部递归的使用 仅限Θ(logn)空间。(注意当 操作链表，归并排序 只需要少量恒定的量 辅助存储)

维基百科的解释是:

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

快速排序

Mergesort

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

虽然它们都在相同的复杂度类中，但这并不意味着它们都具有相同的运行时。快速排序通常比归并排序更快，因为它更容易编写紧凑的实现代码，它所做的操作也更快。这是因为快速排序通常更快，人们使用它而不是归并排序。

然而!我个人经常会使用归并排序或快速排序变体，当快速排序表现不佳时，它们会降级为归并排序。记住。在平均上，快速排序仅为O(n log n)。最坏情况是O(n²)归并排序总是O(n log n)。在实时性能或响应性是必须的，并且您的输入数据可能来自恶意来源的情况下，你不应该使用普通的快速排序。

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

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

所有排序算法都有其起伏。请参阅维基百科上关于排序算法的文章以获得良好的概述。

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

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

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

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

1 Sedgewick，算法

快速排序有O(n²)最差情况运行时和O(nlogn)平均情况运行时。然而，在许多情况下，它优于归并排序，因为许多因素影响算法的运行时，并且，当把它们放在一起时，快速排序胜出。

特别地，经常被引用的排序算法运行时指的是对数据进行排序所需的比较次数或交换次数。这确实是一个很好的性能衡量标准，特别是因为它独立于底层硬件设计。然而，其他的事情——比如引用的局部性(例如，我们是否读取了大量可能在缓存中的元素?)——在当前硬件上也扮演着重要的角色。快速排序特别需要很少的额外空间，并显示出良好的缓存局部性，这使得它在许多情况下比归并排序更快。

此外，通过使用适当的枢轴选择，几乎完全避免快速排序的O(n²)的最坏情况运行时间是非常容易的——例如随机选择它(这是一个极好的策略)。

在实践中，许多现代的快速排序实现(特别是libstdc++的std::sort)实际上是introsort，其理论上的最坏情况是O(nlogn)，与归并排序相同。它通过限制递归深度来实现这一点，一旦它超过logn，就切换到不同的算法(堆排序)。

快速排序并不比归并排序好。对于O(n²)(很少发生的最坏情况)，快速排序可能比归并排序的O(nlogn)慢得多。快速排序的开销更小，所以对于小n和速度较慢的计算机，它会更好。但是今天的计算机是如此之快，以至于合并排序的额外开销可以忽略不计，并且在大多数情况下，非常慢的快速排序的风险远远超过合并排序的微不足道的开销。

此外，归并排序将具有相同键的项按原始顺序保留，这是一个有用的属性。

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

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

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

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

正如许多人所注意到的，快速排序的平均情况性能要比归并排序快。但这只在你假设需要常数的时间来访问任何一块内存时才成立。

在RAM中，这种假设通常不太坏(由于缓存的存在，这种假设并不总是正确的，但也不太坏)。然而，如果你的数据结构足够大，可以存储在磁盘上，那么快速排序得到杀了，因为你的平均磁盘每秒进行200次随机查找。但是，同样的磁盘在按顺序每秒读取或写入兆字节的数据方面没有任何问题。这正是归并排序所做的。

因此，如果数据必须在磁盘上排序，你真的，真的想使用归并排序的一些变体。(通常你快速排序子列表，然后开始将它们合并到某个大小阈值以上。)

此外，如果你必须对这种大小的数据集执行任何东西，请仔细考虑如何避免查找磁盘。例如，这就是为什么在数据库中加载大数据之前先删除索引，然后再重新构建索引的标准建议。在加载期间维护索引意味着不断地查找磁盘。相比之下，如果删除索引，则数据库可以先对要处理的信息排序(当然是使用归并排序!)，然后将其加载到索引的BTREE数据结构中，从而重新构建索引。(btree是自然有序的，所以你可以从一个排序的数据集中加载一个到磁盘上。)

在许多情况下，了解如何避免磁盘寻道使我将数据处理工作花费数小时而不是数天或数周。

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

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

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

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

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

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

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

这很难说。MergeSort最糟糕的是n(log2n)-n+1，如果n等于2^k，这是准确的(我已经证明了这一点)。对于任意n，它在(nlgn - n + 1)和(nlgn + n + O(lgn))之间。但对于quickSort，最好的是nlog2n(也是n = 2^k)。如果你用归并排序除以快速排序，当n是无穷大时，它等于1。这就好像归并排序的最差情况要比快速排序的最佳情况好，我们为什么要用快速排序呢?但是请记住，MergeSort并没有到位，它需要2n的内存空间。MergeSort也需要做很多数组拷贝，我们在算法分析中没有包括这些拷贝。总之，归并排序在理论上确实比快速排序快，但实际上你需要考虑内存空间，数组复制的成本，归并比快速排序慢。我曾经做过一个实验，随机类给我1000000个java数字，归并排序花了2610ms，快速排序花了1370ms。

答案将略微倾向于快速排序w.r.t的变化带来的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

快速排序是最坏情况O(n²)，然而，平均情况始终执行归并排序。每个算法都是O(nlogn)，但你需要记住，当谈论大O时，我们忽略了较低的复杂度因素。当涉及到常数因子时，快速排序比归并排序有显著的改进。

归并排序也需要O(2n)内存，而快速排序可以就地完成(只需要O(n))。这是快速排序通常比归并排序更受欢迎的另一个原因。

额外信息:

快速排序的最坏情况发生在枢轴选择不佳时。考虑下面的例子:

[5,4,3,2,1]

如果主元被选为组中最小或最大的数，那么快速排序将以O(n²)为单位运行。选择列表中最大或最小的25%的元素的概率是0.5。这使得算法有0.5的机会成为一个好的主元。如果我们使用一个典型的主元选择算法(比如选择一个随机元素)，我们有0.5的机会为每个选择的主元选择一个好的主元。对于一个大的集合，总是选择一个糟糕的枢轴的概率是0.5 * n。基于这个概率，快速排序对于平均(和典型)情况是有效的。

为什么快速排序很好?

• 快速排序在最坏情况下需要N^2，在平均情况下需要NlogN。最坏的情况发生在对数据进行排序时。 这可以在开始排序之前通过随机洗牌来缓解。李< / >
• 快速排序不会占用归并排序所占用的额外内存。
• 在数据集较大且数据项相同的情况下，采用三向分区的方法降低了快速排序的复杂度。相同的物品越多越好。如果所有项都相同，则按线性时间排序。[这是大多数库的默认实现]

快速排序总是比归并排序好吗?

不是真的。

• 归并排序是稳定的，但快速排序不是。所以如果你需要输出的稳定性，你可以使用归并排序。在许多实际应用中需要稳定性。
• 现在内存很便宜。因此，如果Mergesort使用的额外内存对您的应用程序不是至关重要的，那么使用Mergesort也没有什么害处。

在java中，Arrays.sort()函数对基本数据类型使用快速排序，对对象数据类型使用归并排序。因为对象消耗内存开销，所以为归并排序增加一点开销对于性能来说可能不是什么问题。

参考:观看第三周，Coursera上的普林斯顿算法课程的快速排序视频

快速排序和合并排序的小增加。

它还可以依赖于排序项的类型。如果访问项、交换和比较不是简单的操作，就像比较平面内存中的整数一样，那么归并排序可能是更可取的算法。

例如，我们在远程服务器上使用网络协议对项目进行排序。

我想在现有的优秀答案中添加一些关于快速排序在偏离最佳情况时的表现以及这种情况的可能性的数学，我希望这将帮助人们更好地理解为什么O(n²)情况在更复杂的快速排序实现中不是真正的问题。

除了随机访问问题之外，还有两个主要因素会影响快速排序的性能，它们都与主元与正在排序的数据的比较有关。

1)数据中键的数量较少。在普通的2分区快速排序中，所有相同值的数据集将在n^2的时间内排序，因为除了枢轴位置之外的所有值每次都放在一边。现代实现通过使用3分区排序等方法来解决这个问题。这些方法在O(n)时间内对所有相同值的数据集执行。因此，使用这样的实现意味着带有少量键的输入实际上提高了性能时间，不再是一个问题。

2)极差的枢轴选择会导致最坏情况的性能。在理想的情况下，主元总是这样，50%的数据是小的，50%的数据是大的，这样在每次迭代中输入将被分成两半。这给了我们n次比较和交换，乘以log-2(n)次递归，时间为O(n*logn)。

非理想的枢轴选择对执行时间的影响有多大?

让我们考虑这样一种情况，其中始终选择主元，这样75%的数据都在主元的一边。它仍然是O(n*logn)但现在对数的底变成了1/0.75或1.33。改变基数时性能的关系始终是一个常数，用log(2)/log(newBase)表示。在这个例子中，这个常数是2.4。所以这种枢轴选择的时间是理想情况的2.4倍。

情况多快会恶化?

不是很快，直到主元选择(始终)非常糟糕:

• 一侧50%:(理想情况下)
• 75%在一边:2.4倍长
• 90%在一边:6.6倍长
• 95%在一边:13.5倍长
• 一边99%长69倍

当我们在一边接近100%时，执行的log部分接近n，整个执行渐近接近O(n²)。

在简单的快速排序实现中，例如排序数组(用于第一个元素枢轴)或反向排序数组(用于最后一个元素枢轴)将可靠地产生最坏情况下O(n^2)的执行时间。此外，具有可预测的枢轴选择的实现可能受到旨在产生最坏情况执行的数据的DoS攻击。现代实现通过各种方法来避免这种情况，例如在排序前对数据进行随机化，从3个随机选择的索引中选择中位数，等等。在混合随机化的情况下，我们有两种情况:

• 小数据集。最坏的情况是可能的但O(n²)不是灾难性的因为n足够小，所以n²也很小。
• 大数据集。最坏的情况在理论上是可能的，但在实践中并非如此。

我们看到糟糕表现的可能性有多大?

机会是低到可以忽略不计。让我们考虑5000个值:

我们假设的实现将使用3个随机选择的索引的中位数来选择一个主元。我们认为在25%-75%范围内的枢轴是“好的”，而在0%-25%或75%-100%范围内的枢轴是“坏的”。如果你使用3个随机索引的中位数来观察概率分布，每次递归都有11/16的机会最终得到一个好的主元。让我们做两个保守的(错误的)假设来简化数学:

1. 好的枢轴总是精确地在25%/75%的分割和2.4*理想情况下运行。我们从来没有得到过理想的分割或者比25/75更好的分割。

2. 糟糕的枢轴总是最坏的情况，基本上对解决方案没有任何贡献。

我们的快速排序实现将在n=10时停止，并切换到插入排序，因此我们需要22个25%/75%的枢轴分区来分解5000个输入值。(10*1.333333^22 > 5000)或者，我们需要4990个最坏情况的枢轴。请记住，如果我们在任何时候处累积了22个好的枢轴，那么排序将完成，所以最坏的情况或接近它的情况需要极坏运气。如果我们需要88次递归才能真正实现22个良好的轴点，以排序到n=10，这将是4*2.4*理想情况，或者大约是理想情况执行时间的10倍。不在88次递归后实现所需的22个良好的枢轴的可能性有多大?

二项概率分布可以回答这个问题，答案大约是10^-18。(n是88,k是21,p是0.6875)你的用户在点击[SORT]的1秒内被闪电击中的可能性大约是他们看到5000项排序运行更糟的1000倍，而不是10*理想情况。随着数据集变大，这种可能性会越来越小。以下是一些数组大小以及它们运行时间超过10*理想值的相应机会:

• 640项数组:10^-13(需要在60次尝试中获得15个良好的枢轴点)
• 5000项数组:10^-18(需要在88次尝试中有22个良好的枢轴)
• 40000项的数组:10^-23(需要在116个中有29个好的枢轴)

记住，这是有两个保守的假设，比现实更糟糕。因此，实际性能更好，剩余概率的平衡更接近理想。

最后，正如其他人所提到的，如果递归堆栈太深，即使这些荒谬的不太可能的情况也可以通过切换到堆排序来消除。因此TLDR是，对于快速排序的良好实现，最坏的情况其实并不存在，因为它已经被设计出来，执行在O(n*logn)时间内完成。

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

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

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

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

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

考虑一下快速排序算法:

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

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

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

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

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

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

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

快速排序是一种就地排序算法，因此它更适合于数组。另一方面，归并排序需要额外的O(N)存储空间，更适合于链表。

与数组不同，在喜欢列表中，我们可以在中间插入O(1)空间和O(1)时间的项，因此归并排序中的归并操作可以在不需要任何额外空间的情况下实现。但是，为数组分配和取消分配额外空间会对归并排序的运行时间产生不利影响。归并排序也有利于链表，因为数据是按顺序访问的，没有太多的随机内存访问。

另一方面，快速排序需要大量的随机内存访问，而使用数组，我们可以直接访问内存，而不需要像链表那样进行任何遍历。同样，快速排序用于数组时具有良好的引用局部性，因为数组连续存储在内存中。

尽管这两种排序算法的平均复杂度都是O(NlogN)，但通常人们在执行普通任务时使用数组进行存储，因此快速排序应该是首选算法。

编辑:我刚刚发现归并排序最差/最好/平均情况总是nlogn，但快速排序可以从n2(最坏的情况下，元素已经排序)到nlogn(平均/最佳情况下，pivot总是将数组分为两半)。

这是一个相当老的问题，但因为我最近处理了这两个问题，所以这里是我的2c:

归并排序平均需要~ N log N次比较。对于已经(几乎)排序过的排序数组，这可以达到1/ 2nlog N，因为在归并时，我们(几乎)总是选择“左边”的1/ 2n次，然后只复制右边1/ 2n个元素。此外，我可以推测，已经排序的输入使处理器的分支预测器发光，但猜测几乎所有的分支都正确，从而防止管道停顿。

快速排序平均需要~ 1.38 nlog N个比较。在比较方面，它不会从已经排序的数组中获得很大的好处(但是在交换方面，可能在CPU内部的分支预测方面，它会获得很大的好处)。

我在相当现代的处理器上的基准测试显示如下:

当比较函数是回调函数时(如qsort() libc实现)，对于随机输入，快速排序比归并排序慢15%，对于已经排序的64位整数，快排序比归并排序慢30%。

另一方面，如果比较不是回调，我的经验是快速排序优于归并排序高达25%。

然而，如果你的(大)数组只有很少的唯一值，归并排序在任何情况下都开始超过快速排序。

因此，底线可能是:如果比较是昂贵的(例如，回调函数，比较字符串，比较结构的许多部分，主要是得到第二个，第三个，第四个“if”来产生差异)-很可能你会更好地使用归并排序。对于简单的任务，快速排序会更快。

以上所说的都是真的: -快速排序可以是N^2，但Sedgewick声称，一个好的随机实现有更多的机会，计算机执行排序被闪电击中比N^2 - Mergesort需要额外的空间

其中一个原因更具有哲学意义。快速排序是自上而下的哲学。有n个元素要排序，总共有n个!的可能性。m & 2个分区;N-m是互斥的，可能性的数量下降了几个数量级。米!* (n - m) !比n小几个数量级!一个人。想象5 !对3 !* 2 !5 !有10倍的可能性比2分区的2 &每人3个。并推断出100万阶乘与900K!*100K!因此，与其担心在某个范围或分区内建立任何秩序，不如在分区中更广泛的层面上建立秩序，并减少分区内的可能性。如果分区本身不是互斥的，那么之前在范围内建立的任何顺序稍后都会被打乱。

任何自下而上的排序方法，如归并排序或堆排序，就像工人或雇员的方法一样，人们很早就开始在微观层面进行比较。但是，一旦在它们之间发现了一个元素，这个顺序就必然会丢失。这些方法是非常稳定的。非常可预测，但要做一定的额外工作。

快速排序: 时间复杂度:O(n²)， 空间复杂度:O(n)

因此，在许多应用中，快速排序是首选，而不是归并排序。

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

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

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

3-参考地点:快速排序特别表现出良好的缓存局部性，这使得它在许多情况下比归并排序更快，比如在虚拟内存环境中。

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