关于算法：为什么quicksort比mergesort更好？

我在一次采访中被问到这个问题。它们都是O(nlogn)，但大多数人使用QuickSort而不是MergeSort。为什么会这样？

正如许多人所指出的，QuickSort的平均案例性能比MergeSort快。但是，只有当您假定有恒定的时间按需访问任何一段内存时，这才是正确的。

在RAM中，这种假设通常不太糟糕(由于缓存，这种假设并不总是正确的，但也不太糟糕)。但是，如果您的数据结构足够大，能够在磁盘上生存，那么QuickSort会因为您的平均磁盘每秒执行200次随机查找而被扼杀。但同样的磁盘在按顺序读取或写入每秒兆字节的数据时没有问题。这正是MergeSort所做的。

因此，如果必须在磁盘上对数据进行排序，那么您确实需要在mergesort上使用一些变体。(通常，您快速排序子列表，然后在某个大小阈值以上将它们合并在一起。)

此外，如果您必须对该大小的数据集做任何事情，请仔细考虑如何避免查找磁盘。例如，这就是为什么在数据库中进行大数据加载之前删除索引，然后稍后重建索引是标准建议的原因。在加载期间维护索引意味着不断地寻找磁盘。相反，如果删除索引，那么数据库可以通过首先对要处理的信息进行排序(当然是使用mergesort！)来重建索引。然后将其加载到索引的btree数据结构中。(btrees是自然保持有序的，因此您可以从排序的数据集中加载一个，很少搜索到磁盘。)

在很多情况下，了解如何避免磁盘查找会让我使数据处理工作花费数小时而不是数天或数周。

QuickSort有O(n2)最坏情况运行时和O(nlogn)平均情况运行时。然而，在许多场景中合并排序更为优越，因为许多因素都会影响算法的运行时，并且在将它们放在一起时，Quicksort会胜出。

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

此外，使用适当的轴选择(如随机选择)可以很容易地避免QuickSort的最坏运行时间O(n2)，几乎完全是这样(这是一个很好的策略)。

在实践中，许多QuickSort的现代实现(特别是libstdc++'s std::sort)实际上是IntroSort，其理论上的最坏情况是O(nlogn)，与合并排序相同。它通过限制递归深度来实现这一点，并在超过logn时切换到另一种算法(heapsort)。

实际上，quicksort是o(n2)。它的平均运行时间是O(nlog(n))，但最坏的情况是O(n2)，当您在包含少数唯一项的列表上运行它时，会发生这种情况。随机化采用O(N)。当然，这不会改变最坏的情况，它只是防止恶意用户让您的排序需要很长时间。

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

但大多数人使用快速排序而不是合并排序。为什么？"

一个尚未给出的心理原因就是流沙的名字更为巧妙。即良好的市场营销。

是的，带有三部分的快速排序可能是最好的通用排序算法之一，但是没有什么能克服"快速"排序听起来比"合并"排序更强大的事实。

正如其他人所指出的，快速排序的最坏情况是O(n^2)，而mergesort和heapsort则保持在O(nlogn)。然而，在一般情况下，这三种情况都是O(nlogn)；因此，它们适用于绝大多数可比较的情况。

使QuickSort平均更好的是，内部循环意味着将多个值与单个值进行比较，而在其他两个术语中，每个比较的两个术语都不同。换句话说，QuickSort的读取次数是其他两种算法的一半。在现代CPU上，性能主要由访问时间决定，因此归根结底，Quicksort是一个很好的第一选择。

我想补充一下到目前为止提到的三种算法(mergesort、quicksort和heap sort)，只有mergesort是稳定的。也就是说，对于具有相同键的值，顺序不会改变。在某些情况下，这是可取的。

但是，事实上，在实际情况下，大多数人只需要很好的平均表现，快速排序是…快速=)

所有排序算法都有其优缺点。请参阅维基百科文章了解排序算法的一个很好的概述。

从QuickSort上的维基百科条目：

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

穆！QuickSort并不比MergeSort更好，它非常适合不同类型的应用程序。

Mergesort is worth considering if speed is of the essence, bad worst-case performance cannot be tolerated, and extra space is available.1

你说他们？他们都是O(非签名)[…]？这是错误的。？在最坏情况下，QuickSort使用大约n^2/2的比较。？1。

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

1 Sedgewick，算法

快速排序是最快的排序算法在实践中，但有许多病理情况，可以使其执行不如O(n2)。

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

维基百科的解释是：

Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the probability of requiring quadratic time.

快速排序

归并排序

我认为MergeSort(即Ω(n))所需的存储量也存在问题，而QuickSort实现没有。在最坏的情况下，它们的算法时间相同，但mergesort需要更多的存储空间。

我想在现有的很好的答案中添加一些关于Quicksort在偏离最佳情况时的表现以及偏离最佳情况的可能性的数学，我希望这将帮助人们更好地理解为什么在更复杂的Quicksort实现中O(N^2)情况并不真正令人关注。好的。

除了随机访问问题外，有两个主要因素会影响QuickSort的性能，它们都与透视图与正在排序的数据的比较方式有关。好的。

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%时，执行的日志部分接近n，整个执行渐进接近o(n^2)。好的。

在QuickSort的简单实现中，排序数组(对于第一个元素透视)或反向排序数组(对于最后一个元素透视)等情况将可靠地产生最坏的O(n^2)执行时间。此外，具有可预测的透视选择的实现可能会受到DoS攻击，这些数据旨在产生最坏的执行情况。现代的实现通过多种方法来避免这一点，例如在排序前随机化数据、选择3个随机选择的索引的中位数等。通过这种组合的随机化，我们有2个案例：好的。

• 小数据集。最坏的情况是可能的，但O(n^2)不是灾难性的，因为n足够小，n^2也很小。
• 大数据集。最坏的情况在理论上是可能的，但在实践中却不可能。

我们看到糟糕表现的可能性有多大？好的。

机会很小。让我们考虑一种5000个值：好的。

我们假设的实现将使用3个随机选择的索引的中位数来选择一个支点。我们将把25%-75%范围内的支点视为"好的"，将0%-25%或75%-100%范围内的支点视为"坏的"。如果您使用3个随机索引的中位数查看概率分布，那么每个递归都有11/16的机会以一个好的轴结束。让我们做两个保守(和错误)假设来简化数学：好的。

我们的QuickSort实现将在n=10停止，并切换到插入排序，因此我们需要22个25%/75%的透视分区来将5000个值的输入中断到目前为止。(10*1.333333^22>5000)或者，我们需要4990个最坏情况的支点。请记住，如果我们在任何时候积累了22个好的支点，那么分类就会完成，所以最坏的情况或任何接近它的情况都需要非常坏的运气。如果我们用88个递归来实际实现排序为n=10所需的22个好的数据透视，那么这将是4*2.4*理想情况或大约是理想情况执行时间的10倍。88次递归之后，我们有多可能无法实现所需的22个好的数据透视？好的。

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

• 640个项目的数组：10^-13(60次尝试中需要15个良好的轴点)
• 5000个项目的数组：10^-18(88次尝试中需要22个良好的旋转)
• 40000个项目的阵列：10^-23(需要116个中29个良好的枢轴)

记住，这有两个比实际情况更糟的保守假设。所以实际性能更好，剩余概率的平衡更接近理想。好的。

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

QuickSort并不比MergeSort好。对于O(n^2)(很少发生的最坏情况)，快速排序可能比合并排序的O(nlogn)慢得多。QuickSort的开销更少，因此对于小型n和慢速计算机来说，它更好。但是现在的计算机速度如此之快，合并排序的额外开销可以忽略不计，在大多数情况下，非常缓慢的快速排序的风险远远超过合并排序的微不足道的开销。

此外，mergesort使具有相同键的项保持其原始顺序，这是一个有用的属性。

在合并排序中，一般的算法是：

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

低于这一级别，步骤3的每次迭代都涉及处理n/2元素，但您必须重复此过程两次。所以你仍然要处理2*n/2==n个元素。

低于这个级别，您将合并4*n/4==n个元素，依此类推。递归堆栈中的每个深度都涉及合并相同数量的元素，跨越对该深度的所有调用。

考虑使用快速排序算法：

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

低于这个水平，你要处理的是2个子数组，它们的组合大小为n-1(即减去前面的轴点)。为每个子数组选择一个轴点，最多可获得两个额外的轴点。

低于这一级别，您将处理4个子数组，它们的组合大小为n-3，原因与上面相同。

然后N-7…然后N-15…然后N-32…

递归堆栈的深度保持大致相同(logn)。对于合并排序，您总是在递归堆栈的每个级别上处理一个n元素合并。但是，通过快速排序，处理的元素数量会随着堆栈的深入而减少。例如，如果查看递归堆栈中间的深度，则要处理的元素数为n-2^((logn)/2))==n-sqrt(n)。

免责声明：在合并排序时，由于每次将数组分成2个完全相等的块，递归深度正好是logn。在快速排序时，因为您的透视点不可能正好位于数组的中间，所以递归堆栈的深度可能略大于logn。我还没有做过数学计算来看看这个因素和上面描述的因素在算法的复杂性中究竟扮演了多大的角色。

对于原始值的dualPivotQuicksort所带来的变化，答案将略微倾向于Quicksort w.r.t。它在Java 7中用于Java.UTIL数组中的排序。

您可以在这里找到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(n^2)，这是在数组已经排序时发生的。

快速排序具有更好的平均大小写复杂性，但在某些应用程序中，它是错误的选择。QuickSort易受拒绝服务攻击。如果攻击者可以选择要排序的输入，那么他可以很容易地构造一个集，该集的时间复杂度最差为O(n^2)。

MergeSort的平均情况复杂性和最坏情况复杂性是相同的，因此不会遇到相同的问题。合并排序的这一特性也使它成为实时系统的首选——正是因为没有病理情况导致它运行得慢得多。

因为这些原因，我比我更喜欢mergesort。

虽然它们都在同一个复杂度类中，但这并不意味着它们都有相同的运行时。QuickSort通常比MergeSort更快，这是因为它更容易对紧凑的实现进行编码，并且它所做的操作可以更快。这是因为快速排序通常更快，人们使用它而不是合并排序。

然而！我个人经常会使用mergesort或一个quicksort变体，当quicksort做得不好时，它会降级为mergesort。记得。QuickSort平均只有O(n logn)。最坏的情况是O(n^2)！mergesort总是o(n log n)。如果必须提供实时性能或响应，并且输入数据可能来自恶意源，则不应使用普通的快速排序。

当我对这两种排序算法进行试验时，通过计算递归调用的数量，与mergesort相比，quicksort始终具有较少的递归调用。这是因为QuickSort有数据透视，并且数据透视不包含在下一个递归调用中。这样，QuickSort可以比MergeSort更快地到达递归基本情况。

这是一个相当古老的问题，但由于我最近已经处理了这两个问题，下面是我的2c：

合并排序平均需要~n个日志n个比较。对于已经(几乎)排序的数组，这会下降到1/2n logn，因为在合并时，我们(几乎)总是选择"左"部分1/2n次，然后只复制右1/2n个元素。此外，我可以推测，已经排序的输入会使处理器的分支预测器亮起，但可以正确猜测几乎所有分支，从而防止管道阻塞。

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

我在相当现代的处理器上的基准显示了以下内容：

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

另一方面，如果比较不是回调，我的经验是QuickSort比MergeSort高出25%。

但是，如果您的(大)数组只有很少的唯一值，那么合并排序在任何情况下都会开始超越快速排序。

因此，底线可能是：如果比较比较成本高昂(例如，回调函数、比较字符串、比较结构的许多部分，大多数情况下都是为了获得第二个三分之一的"if"，从而产生差异)，那么合并排序可能会更好。对于更简单的任务，快速排序将更快。

也就是说之前说的都是真的：-quicksort可以是n^2，但是sedgewick声称一个好的随机实现比n^2更有可能被闪电击中。-MergeSort需要额外的空间

快速排序是最坏的情况O(n^2)，但是，平均情况总是执行合并排序。每个算法都是O(nlogn)，但您需要记住，当谈论大O时，我们会忽略较低的复杂性因素。在常数因子方面，快速排序比合并排序有显著的改进。

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

额外信息：

快速排序的最坏情况发生在轴选择不当的情况下。请考虑以下示例：

〔5, 4, 3，2, 1〕

如果将数据透视选择为组中最小或最大的数字，则快速排序将在o(n^2)中运行。选择列表中最大或最小25%的元素的概率为0.5。这给了算法0.5的机会成为一个好的支点。如果我们使用一个典型的轴选择算法(比如选择一个随机元素)，我们有0.5的机会为每个轴选择一个好的轴。对于大尺寸的集合，总是选择糟糕的轴的概率为0.5*N。基于此概率，快速排序对于平均(和典型)情况是有效的。

为什么流沙是好的？

• 在最坏情况下，快速排序需要n^2，而在平均情况下则需要n^2。最坏的情况发生在数据排序时。这可以通过在开始排序之前随机无序排列来减轻。
• QuickSort不占用合并排序所占用的额外内存。
• 如果数据集很大，并且有相同的项，那么使用3路分区可以降低快速排序的复杂性。相同项目的编号越多，排序越好。如果所有项目都相同，则按线性时间排序。[这是大多数库中的默认实现]

QuickSort总是比MergeSort好吗？

不是真的。

• MergeSort稳定，但QuickSort不稳定。所以，如果需要输出的稳定性，可以使用mergesort。在许多实际应用中，稳定性是必需的。
• 现在记忆很便宜。因此，如果MergeSort使用的额外内存对应用程序不重要，那么使用MergeSort不会有任何危害。

注意：在Java中，数组.SoTo()函数使用原始数据类型的QueQuote和对象数据类型的合并。因为对象消耗内存开销，所以为mergesort添加一点开销对于性能来说可能不是什么问题。

参考：观看第3周的快速排序视频，普林斯顿算法课程在Coursera

所有事物都是平等的，我希望大多数人使用任何最方便的东西，而这往往是qsort(3)。除此之外，已知QuickSort在数组上速度非常快，就像MergeSort是列表的常见选择一样。

我想知道的是为什么很少看到基数或桶排序。它们是O(N)，至少在链表上是O(N)，它所需要的只是一些将键转换为序数的方法。(字符串和浮点数工作正常。)

我认为原因与计算机科学的教学方式有关。我甚至不得不向我的演讲者证明算法分析确实可以比O(n log(n))更快地排序。(他有证据表明你不能比O(n log(n))更快地进行比较排序，这是真的。)

在另一个新闻中，浮点数可以被排序为整数，但之后必须将负数转过来。

编辑：实际上，这里还有一种更为恶毒的方法来将浮点数排序为整数：http://www.stereopsis.com/radix.html。请注意，不管您实际使用什么排序算法，都可以使用位翻转技巧…

很难说。mergesort的最坏情况是n(log2n)-n+1，如果n等于2^k，这是准确的(我已经证明了这一点)。对于任何n，它介于(n lg n-n+1)和(n lg n+n+o(lg n))之间。但是对于quicksort，它的最好情况是n log2n(也就是n等于2^k)。如果用quicksort除mergesort，当n为无穷大时，它等于1。所以它就好像是MergeSort比QuickSort的最佳情况要好，我们为什么要使用QuickSort？但请记住，mergesort不在适当的位置，它需要2n内存空间。而且mergesort还需要做许多数组副本，我们在算法分析中不包括这些副本。总之，mergesort在Theroy中确实比quick sort快，但实际上你需要考虑内存空间，数组副本的成本，合并比快速排序慢。我曾经做过一个在实验中，我在Java中通过随机类得到1000000位数字，并且通过GysErrt，1370Ms通过Quasy排序得到2610Ms。

快速与合并排序的小添加。

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

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

此外，在像"链接列表"这样的自定义容器中，快速排序没有好处。1。合并对链接列表排序，不需要额外的内存。2。对快速排序中的元素的访问不是连续的(内存中)

同时考虑时间和空间的复杂性。对于合并排序：时间复杂度：o(nlogn)空间复杂性：o(nlogn)

对于快速排序：时间复杂度：o(n^2)空间复杂性：O(N)

现在，他们都在一个场景中取胜。但是，使用一个随机的支点，你几乎总是可以将快速排序的时间复杂性降低到o(nlogn)。

因此，在许多应用程序中，快速排序优先于合并排序。

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

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

另一方面，快速排序需要大量的随机内存访问，使用数组，我们可以直接访问内存，而不需要按照链表的要求进行任何遍历。当用于数组时，由于数组是连续存储在内存中，所以快速排序具有良好的引用位置。

尽管这两种排序算法的平均复杂度都是O(nlogn)，但通常普通任务的人使用一个数组来存储，因此快速排序应该是首选算法。

编辑：我刚发现合并排序最差/最佳/平均大小写总是非登录的，但快速排序可以从n2(当元素已经排序时最差的情况)到非登录(当pivot总是将数组分为两部分时，平均/最佳大小写)不等。

在C/C++字段中，当不使用STL容器时，我倾向于使用QueQuess，因为它是内置的。进入运行时，而mergesort不是。

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

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

其中一个原因是更加哲学化。流沙是自上而下的哲学。有n个要排序的元素，就有n个！可能性。由于M&N-M的两个分区相互排斥，因此可能性的数量以几个数量级下降。M！*(N-M)！比N小几个订单！独自一人。想象一下5！VS 3！* 2！5！比两个分区(每个分区2&3)的可能性大10倍。并推断出100万阶乘与90万！* 100K！与之相反，不要担心在一个范围或分区内建立任何顺序，只需在更广泛的分区级别上建立顺序，并减少分区内的可能性。如果分区本身不是互斥的，那么在某个范围内较早建立的任何顺序都将在稍后受到干扰。

任何自下而上的排序方法，如合并排序或堆排序，都像工人或雇员的方法，在这种方法中，人们很早就开始在微观层次上进行比较。但是，一旦在它们之间找到一个元素，这个顺序就一定会丢失。这些方法是非常稳定和非常可预测的，但需要做一些额外的工作。

快速排序就像一种管理方法，一个人最初不关心任何订单，只关心满足一个广泛的标准，而不考虑订单。然后缩小分区，直到得到一个排序集。Quicksort真正的挑战是在黑暗中寻找一个分区或标准，而你对要排序的元素一无所知。这就是为什么我们要么花费一些精力去寻找中值，要么随机选择1，要么采取一些任意的"管理"方法。找到一个完美的中位数需要大量的努力，并导致一个愚蠢的自下而上的方法再次。因此，quicksort只说选择一个随机的支点，希望它在中间的某个地方，或者做一些工作来找到3、5或更多的中值，以找到更好的中值，但不打算完美，不要浪费任何时间在最初的排序上。如果你运气好，或者当你没有中位数，但只是抓住机会的时候，有时会降到n^2，这看起来很好。任何方式的数据都是随机的。正确的。因此，我更赞同QuickSort的自上而下逻辑方法，结果发现，它所节省的数据透视选择和比较的机会似乎比任何细致彻底的、稳定的、自底向上的方法(如合并排序)更有效。但是