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.
27 回答
实际上，QuickSort是O（n2） . 它的平均案例运行时间是O（nlog（n）），但最坏的情况是O（n2），当你在包含很少的唯一项目的列表上运行它时会发生这种情况 . 随机化需要O（n） . 当然，这并没有改变它最糟糕的情况，它只是防止恶意用户花费很长时间进行排序 .
QuickSort更受欢迎，因为它：
就地（MergeSort需要额外的内存线性到要排序的元素数） .
有一个小的隐藏常数 .
“然而大多数人使用Quicksort而不是Mergesort . 为什么会这样？”
没有给出的一个心理原因就是Quicksort更加巧妙地命名 . 即良好的营销 .
是的，具有三重分区的Quicksort可能是最好的通用排序算法之一，但是没有克服“快速”排序听起来比“合并”排序更强大的事实 .
Quicksort具有O（n2）最坏情况运行时和O（nlogn）平均情况运行时 . 但是，它在许多场景中优于合并排序，因为许多因素会影响算法的运行时间，并且当将它们全部放在一起时，快速排序会胜出 .
特别地，经常引用的排序算法运行时指的是执行排序数据所需的比较次数或交换次数 . 这确实是衡量性能的一个很好的指标，特别是因为它独立于底层硬件设计 . 但是，其他的东西 - 比如引用的位置（即我们读取了很多可能在缓存中的元素？） - 在当前的硬件上也扮演着重要的角色 . Quicksort特别需要很少的额外空间并且具有良好的缓存局部性，这使得它在许多情况下比合并排序更快 .
此外，通过使用适当的枢轴选择 - 例如随机选择（这是一个很好的策略），很容易避免快速排序的O（n2）的最坏情况运行时间 .
在实践中，许多现代的快速排序实现（特别是libstdc的
std::sort）实际上是introsort，其理论最坏情况是O（nlogn），与合并排序相同 . 它通过限制递归深度来实现这一点，并且一旦超过logn就切换到不同的算法（heapsort） .正如许多人所指出的，快速排序的平均案例性能比mergesort快 . But 这是唯一的，如果你假设有时间按需访问任何内存 .
在RAM中，这个假设通常不是太糟糕（因为缓存并不总是如此，但它并不太糟糕） . 但是，如果您的数据结构足够大，可以存放在磁盘上，那么快速排序会因为您的平均磁盘每秒执行200次随机搜索而被杀死 . 但是同一个磁盘在顺序读取或写入每秒兆字节的数据方面没有问题 . 这正是mergesort的作用 .
因此，如果必须在磁盘上对数据进行排序，那么您真的非常希望在mergesort上使用一些变体 . （通常，您会快速排序子列表，然后开始将它们合并到一些大小阈值之上 . ）
此外，如果您必须对该大小的数据集执行任何操作，请仔细考虑如何避免寻找磁盘 . 例如，这就是为什么在数据库中执行大量数据加载之前删除索引的标准建议，然后再重建索引 . 在加载期间维护索引意味着不断寻求磁盘 . 相比之下，如果删除索引，那么数据库可以通过首先对要处理的信息进行排序（当然使用mergesort！）然后将其加载到索引的BTREE数据结构中来重建索引 . （BTREE自然是按顺序保存的，因此您可以从排序的数据集中加载一个，只需很少的搜索到磁盘 . ）
在很多情况下，理解如何避免磁盘搜索让我使数据处理工作需要数小时而不是数天或数周 .
正如其他人所说，Quicksort的最坏情况是O（n ^ 2），而mergesort和heapsort留在O（nlogn） . 然而，在一般情况下，所有三个都是O（nlogn）;所以他们对绝大多数情况都具有可比性 .
使Quicksort平均更好的原因是内循环意味着将几个值与单个值进行比较，而另外两个值对于每个值都不同比较 . 换句话说，Quicksort读取的数量是其他两种算法的一半 . 在现代CPU上，性能主要受访问时间的影响，因此最终Quicksort成为首选 .
我想补充到目前为止提到的三个算法（mergesort，quicksort和heap sort），只有mergesort是稳定的 . 也就是说，对于具有相同键的那些值，顺序不会改变 . 在某些情况下，这是可取的 .
但是，说实话，在实际情况下，大多数人只需要良好的平均表现，快速排序就是......快=）
所有排序算法都有其起伏 . 有关概述，请参见Wikipedia article for sorting algorithms .
Mu! Quicksort并不是更好，它比mergesort更适合不同类型的应用程序 .
你说他们“他们都是O（nlogn）[...]» . 这是错的 . «Quicksort在最坏的情况下使用大约n ^ 2/2比较 . »1 .
然而，根据我的经验，最重要的属性是在使用具有命令式范例的编程语言时，可以在排序时轻松实现顺序访问 .
1 Sedgewick，算法
Quicksort是实践中最快的排序算法，但有许多病理案例可以使它的表现与O（n2）一样糟糕 .
保证Heapsort在O（n * ln（n））中运行，并且只需要有限的额外存储空间 . 但是现实世界测试有许多引用表明，heapsort平均比快速排序明显慢 .
从the Wikipedia entry on Quicksort：
维基百科的解释是：
Quicksort
Mergesort
我认为快速排序实现所没有的Mergesort所需的存储量（即Ω（n））也存在问题 . 在最坏的情况下，它们的算法时间相同，但mergesort需要更多的存储空间 .
Quicksort并不比mergesort好 . 使用O（n ^ 2）（最坏情况很少发生），快速排序可能比合并排序的O（nlogn）慢得多 . Quicksort的开销较小，因此对于小型和慢速计算机，它更好 . 但是今天的计算机速度如此之快，以至于mergesort的额外开销可以忽略不计，并且在大多数情况下，快速排序非常慢的风险远远超过了mergesort的微不足道的开销 .
此外，mergesort以原始顺序保留具有相同键的项，这是一个有用的属性 .
我想在现有的优秀答案中添加一些关于QuickSort在与最佳案例分歧时的表现以及可能性如何的数学，我希望这将有助于人们更好地理解为什么O（n ^ 2）案例不是真实的关注更复杂的QuickSort实现 .
除了随机访问问题之外，有两个主要因素会影响QuickSort的性能，它们都与枢轴与正在排序的数据的比较有关 .
1）数据中的少量键 . 所有相同值的数据集将在n ^ 2时间内在vanilla 2分区QuickSort上排序，因为除了数据透视位置之外的所有值每次都放在一侧 . 现代实现通过诸如使用3分区排序的方法来解决此问题 . 这些方法在所有数据集上执行O（n）时间内的值相同 . 因此，使用这样的实现意味着具有少量密钥的输入实际上改善了性能时间并且不再是一个问题 .
2）非常糟糕的枢轴选择会导致最坏的情况 . 在理想情况下，枢轴总是这样，50％的数据更小，50％的数据更大，因此在每次迭代期间输入将被分成两半 . 这给了我们比较和交换时间log-2（n）递归O（n * logn）时间 .
How much does non-ideal pivot selection affect execution time?
让我们考虑这样一种情况，即一致地选择枢轴，使得75％的数据位于枢轴的一侧 . 它仍然是O（n * logn），但现在日志的基数已经变为1 / 0.75或1.33 . 更改base时的性能关系始终是log（2）/ log（newBase）表示的常量 . 在这种情况下，该常数为2.4 . 因此，这种枢轴选择的质量比理想选择长2.4倍 .
How fast does this get worse?
在枢轴选择变得非常糟糕之前不是很快：
一边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也很小 .
大数据集 . 最坏的情况在理论上是可能的，但在实践中却不是 .
How likely are we to see terrible performance?
机会很小 . 让我们考虑一下5,000种值：
我们的假设实现将使用3个随机选择的索引的中值选择一个支点 . 我们将考虑在25％-75％范围内的枢轴为“良好”，并且在0％-25％或75％-100％范围内的枢轴为“差” . 如果你使用3个随机索引的中位数来观察概率分布，每次递归都有11/16的机会以一个好的支点结束 . 让我们做两个保守（和假）假设来简化数学：
良好的枢轴总是精确地处于25％/ 75％的分割，并且在2.4 *理想情况下运行 . 我们永远不会得到理想的分裂或任何超过25/75的分裂 .
坏枢轴总是最坏的情况，基本上对解决方案没有贡献 .
我们的QuickSort实现将在n = 10时停止并切换到插入排序，因此我们需要22个25％/ 75％的透视分区来打破到目前为止的5,000值输入 . （10 * 1.333333 ^ 22> 5000）或者，我们需要4990个最坏情况的支点 . 请记住，如果我们在任何时候积累22个好的枢轴，那么排序将完成，所以最坏的情况或接近它的任何东西都需要非常糟糕的运气 . 如果我们需要88次递归才能真正实现排序到n = 10所需的22个好的枢轴，这将是4 * 2.4 *理想情况或理想情况的执行时间的大约10倍 . 在88次递归后，我们有多大可能无法达到所需的22个好的枢轴？
Binomial probability distributions可以回答这个问题，答案大约是10 ^ -18 . （n是88，k是21，p是0.6875）你的用户在点击[SORT]所需的1秒钟内被闪电击中的可能性大约是他们看到5,000件物品运行更糟糕的一倍超过10 *的理想情况 . 随着数据集变大，这种机会变小 . 以下是一些数组大小及其相应的运行时间超过10 *的机会：
640个项目的数组：10 ^ -13（在60次尝试中需要15个好的轴心点）
5,000件物品的数组：10 ^ -18（在88次尝试中需要22个好的枢轴）
40,000个项目的数组：10 ^ -23（116个中需要29个好的枢轴）
请记住，这是有两个比现实更糟糕的保守假设 . 因此实际表现更好，剩余概率的 balancer 更接近理想 .
最后，正如其他人所提到的，即使是这些荒谬的不可能的案例也可以如果递归堆栈太深，则通过切换到堆排序来消除 . 所以TLDR就是说，对于QuickSort的良好实现，最坏的情况并不存在，因为它已被设计出来并且在O（n * logn）时间内完成执行 .
对于使用DualPivotQuickSort为原始值带来的变化，答案会略微倾向于快速输入w.r.t.它在 JAVA 7 中用于排序 java.util.Arrays
你可以在这里找到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
虽然它们都处于相同的复杂性类中，但这并不意味着它们都具有相同的运行时 . Quicksort通常比mergesort更快，因为它更容易编写严格的实现，并且它所做的操作可以更快 . 这是因为快速排序通常比人们使用它而不是mergesort更快 .
然而！我个人经常会使用mergesort或quicksort变体，当quicksort表现不佳时会降级为mergesort . 记得 . Quicksort平均只有O（n log n） . 最坏的情况是O（n ^ 2）！ Mergesort总是O（n log n） . 如果必须使用实时性能或响应能力，并且您的输入数据可能来自恶意来源， you should not use plain quicksort.
Quicksort具有更好的平均案例复杂性，但在某些应用程序中它是错误的选择 . Quicksort易受拒绝服务攻击 . 如果攻击者可以选择要排序的输入，他可以轻松地构造一个最差情况时间复杂度为o（n ^ 2）的集合 .
Mergesort的平均案例复杂性和最坏情况复杂性是相同的，因此不会遇到同样的问题 . merge-sort的这个属性也使它成为实时系统的最佳选择 - 正是因为没有病态的情况导致它运行得多，慢得多 .
由于这些原因，我是Mergesort的忠实粉丝，而不是Quicksort .
Why Quicksort is good?
QuickSort在最坏的情况下采用N ^ 2和NlogN平均情况 . 最糟糕的情况发生在数据排序时 . 在排序开始之前，可以通过随机混洗来减轻这种情况 .
QuickSort不占用合并排序所占用的额外内存 .
如果数据集很大且项目相同，则Quicksort的复杂性通过使用3路分区而降低 . 更多相同的项目更好的排序 . 如果所有项目都相同，则按线性时间排序 . [这是大多数库中的默认实现]
Is Quicksort always better than Mergesort?
Not really.
Mergesort稳定，但Quicksort不稳定 . 因此，如果您需要输出稳定性，则可以使用Mergesort . 在许多实际应用中需要稳定性 .
记忆现在很便宜 . 因此，如果Mergesort使用的额外内存对您的应用程序并不重要，那么使用Mergesort没有任何害处 .
Note: 在java中，Arrays.sort（）函数使用Quicksort作为基本数据类型，使用Mergesort作为对象数据类型 . 因为对象消耗了内存开销，所以为Mergesort添加一点开销可能不是性能观点的任何问题 .
Reference ：观看Week 3, Princeton Algorithms Course at Coursera的QuickSort视频
快速排序是最坏情况O（n ^ 2），但是，平均情况始终执行合并排序 . 每个算法都是O（nlogn），但你需要记住，在谈论Big O时，我们忽略了较低的复杂因素 . 当涉及常数因素时，快速排序比合并排序有显着改进 .
合并排序还需要O（2n）内存，而快速排序可以就地完成（只需要O（n）） . 这是快速排序通常优于合并排序的另一个原因 .
Extra info:
当枢轴选择不当时，会发生最快的快速排序 . 请考虑以下示例：
[5,4,3,2,1]
如果选择枢轴作为组中的最小或最大数字，则快速排序将在O（n ^ 2）中运行 . 选择列表中最大或最小25％的元素的概率为0.5 . 这使得算法成为一个良好的支点 . 如果我们采用典型的枢轴选择算法（比如选择一个随机元素），我们就有0.5个机会为每个枢轴选择一个好的枢轴 . 对于大尺寸的集合，总是选择不良枢轴的概率是0.5 * n . 基于此概率，快速排序对于平均（和典型）情况是有效的 .
在merge-sort中，通用算法是：
对左子阵列进行排序
对右子阵列进行排序
合并2个排序的子数组
在顶层，合并2个排序的子阵列涉及处理N个元素 .
低于该水平一级，步骤3的每次迭代都涉及处理N / 2个元素，但您必须重复此过程两次 . 所以你还在处理2 * N / 2 == N个元素 .
低于此级别，您将合并4 * N / 4 == N个元素，依此类推 . 递归堆栈中的每个深度都涉及在该深度的所有调用中合并相同数量的元素 .
请考虑使用快速排序算法：
选择一个支点
将轴心点放在数组中的正确位置，左边是所有较小的元素，右边是较大的元素
对左子阵列进行排序
对右子阵列进行排序
在顶层，你正在处理一个大小为N的数组 . 然后你选择一个枢轴点，把它放在正确的位置，然后可以完全忽略它对于算法的其余部分 .
在这之下的一个级别，你要处理2个子组合，这些子组合的大小为N-1（即减去前面的支点） . 您为每个子阵列选择一个轴心点，最多可增加2个轴心点 .
由于与上述相同的原因，您将处理4个组合大小为N-3的子阵列 .
那么N-7 ......那么N-15 ......那么N-32 ......
递归堆栈的深度保持大致相同（logN） . 使用merge-sort，您总是在递归堆栈的每个级别处理N元素合并 . 但是，通过快速排序，当您下到堆栈时，您正在处理的元素数量会减少 . 例如，如果您查看递归堆栈中间的深度，则您要处理的元素数量为N - 2 ^（（logN）/ 2））== N - sqrt（N） .
免责声明：在merge-sort上，因为每次将数组划分为2个完全相等的块，递归深度正好是logN . 在快速排序时，因为您的枢轴点不可能完全位于数组的中间，递归堆栈的深度可能略大于logN . 我没有做过数学计算，看看这个因素和上面描述的因素在算法的复杂性中实际发挥了多大作用 .
当我尝试使用两种排序算法时，通过计算递归调用的数量，quicksort始终比mergesort具有更少的递归调用 . 这是因为quicksort具有枢轴，并且枢轴不包括在下一个递归调用中 . 这样，quicksort可以比mergesort更快地达到递归基本情况 .
与合并排序不同，快速排序不使用辅助空间 . 而Merge Sort使用辅助空间O（n） . 但是Merge Sort具有O（nlogn）的最坏情况时间复杂度，而Quick Sort的最坏情况复杂度是O（n ^ 2），当数组已经被排序时发生 .
在所有条件相同的情况下，我希望大多数人都能使用最方便的东西，而且往往是qsort（3） . 除了快速排序之外，已知数组上的快速排序非常快，就像mergesort是列表的常见选择一样 .
我很少看到radix或桶排序 . 它们是O（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）之间但是对于quickSort，最好的是nlog2n（也就是n等于2 ^ k） . 如果你用QuickSort划分Mergesort，当n是无穷大时它等于1 . 所以就好像最坏的那样MergeSort的情况好于QuickSort的最佳情况，为什么我们使用quicksort？但是请记住，MergeSort不到位，它需要2n memeroy空间 . 而且MergeSort还需要做很多数组副本，我们不包括对于算法的分析 . 总之，MergeSort在理论上比快速排序更加苛刻，但实际上你需要考虑记忆空间，阵列复制的成本，合并比快速排序要慢 . 我曾经做过一个实验，我得到了java中的1000000位数字由Randomclass，由mergesort花了2610ms，由quicksort花了1370ms .
快速与合并排序的小增加 .
它也可以取决于分拣物品的种类 . 如果访问项目，交换和比较不是简单的操作，比如比较平面内存中的整数，那么合并排序可以是更好的算法 .
例如，我们使用远程服务器上的网络协议对项目进行排序 .
此外，在像"linked list"这样的自定义容器中，快速排序也没有好处 .
1.合并链表上的排序，不需要额外的内存 . 2.快速排序中元素的访问不是顺序的（在内存中）
这是一个非常古老的问题，但由于我最近在这里处理了两个问题，我的2c：
合并排序需要平均~N log N比较 . 对于已经（几乎）排序的排序数组，这降低到1/2 N log N，因为在合并时我们（几乎）总是选择“左”部分1/2 N次，然后只复制右1/2 N个元素 . 此外，我可以推测已经排序的输入使处理器的分支预测器闪耀，但几乎所有分支都正确猜测，从而防止管道停滞 .
平均快速排序需要~1.38 N log N比较 . 在比较方面，它没有从已经排序的数组中获益很大（但是它在交换方面确实有用，并且可能在CPU内部的分支预测方面） .
我对相当现代的处理器的基准测试显示如下：
当比较函数是回调函数时（如在qsort（）libc实现中），quicksort比随机输入的mergesort慢15％，对于64位整数，已经排序的数组为30％ .
另一方面，如果比较不是回调，我的经验是quicksort比mergesort高出25％ .
但是，如果您的（大型）数组具有非常少的唯一值，则在任何情况下，合并排序都会开始获得快速排序 .
所以也许底线是：如果比较是昂贵的（例如回调函数，比较字符串，比较结构的许多部分，大多数得到第二个 - 第三个“如果”以产生差异） - 你可能会更好合并排序 . 对于更简单的任务，quicksort会更快 .
这说以前所说的都是真的： - Quicksort可以是N ^ 2，但是Sedgewick声称一个好的随机实现有更多的机会让计算机执行排序被闪电击中而不是去N ^ 2 - Mergesort需要额外的空间
快速排序是一种就地排序算法，因此它更适合于数组 . 另一方面，合并排序需要额外存储O（N），并且更适合链接列表 .
与数组不同，在喜欢的列表中，我们可以使用O（1）空间和O（1）时间在中间插入项目，因此可以在没有任何额外空间的情况下实现合并排序中的合并操作 . 但是，为数组分配和取消分配额外空间会对合并排序的运行时间产生负面影响 . 合并排序也有利于链表，因为数据是按顺序访问的，没有太多的随机内存访问 .
另一方面，快速排序需要大量随机内存访问，并且通过数组，我们可以直接访问内存而无需链接列表所需的任何遍历 . 当用于数组时，快速排序具有良好的引用局部性，因为数组连续存储在存储器中 .
尽管两种排序算法的平均复杂度都是O（NlogN），但普通任务的人通常使用数组进行存储，因此快速排序应该是首选算法 .
编辑：我刚刚发现合并排序最差/最佳/平均情况总是nlogn，但快速排序可以从n2（元素已经排序的最坏情况）到nlogn（avg /最佳情况，当pivot总是将数组分成两个时）半） .
在c / c land中，当不使用stl容器时，我倾向于使用quicksort，因为它是在运行时内置的，而mergesort则不是 .
所以我相信在很多情况下，它只是阻力最小的路径 .
此外，对于整个数据集不适合工作集的情况，快速排序的性能可以更高 .
其中一个原因是更具哲学性 . Quicksort是Top-> Down哲学 . 有n个元素要排序，有n个！可能性 . 由于m＆n-m的2个分区是相互排斥的，因此可能性的数量下降了几个数量级 . 米！ （n-m）！比n少几个订单！单独 . 想象5！ vs 3！ * 2！ 5！比2个分区的2个和3个分区的可能性高10倍 . 并推断到1百万因子与900K！ 100K！因此，不要担心在范围或分区内 Build 任何订单，只需在分区中更广泛的级别 Build 订单，并减少分区内的可能性 . 如果分区本身不是互斥的，则稍后在某个范围内 Build 的任何订单都会受到干扰 .
任何自下而上的订单方法（如合并排序或堆排序）就像 Worker 或员工的方法，其中一个人开始在微观层面提前进行比较 . 但是一旦稍后发现它们之间的元素，这个顺序肯定会丢失 . 这些方法非常稳定且极其可预测，但需要做一些额外的工作 .
快速排序就像管理方法，其中一个人最初并不关心任何订单，只关注满足宽泛的标准而不考虑订单 . 然后缩小分区，直到获得排序集 . Quicksort的真正挑战在于，当您对要排序的元素一无所知时，在黑暗中找到分区或标准 . 这就是为什么我们需要花费一些精力来找到一个中值或随机选择1或一些任意的“管理”方法 . 找到一个完美的中位数可能会花费大量的精力，并导致一个愚蠢的自下而上的方法 . 所以Quicksort只是选择了一个随机的支点，并希望它会在中间位置或者做一些工作来找到中位数为3,5或更多的东西以找到更好的中位数但是不打算完美而且不要浪费任何时候最初订购 . 如果你很幸运，或者当你没有获得中位数但有时候有机会降级到n ^ 2时，这似乎表现得很好 . 任何方式数据都是随机的 . 对 . 因此，我更同意快速排序的顶级 - >向下逻辑方法，并且结果表明，先前节省的枢轴选择和比较所需的机会似乎比任何细致和彻底稳定的底部更好地工作 - >类似方法合并排序 . 但