我在一次采访中被问到这个问题。它们都是O（nlogn），但大多数人使用Quicksort而不是Mergesort。为什么？
为什么快速排序比合并排序好？
原标题：
最佳回答
Quicksort有O（＜i＞n＜/i＞＜sup＞2＜/sup＞）最坏情况运行时间和O（＜i>n＜/i>log＜i＞n
特别是，经常引用的排序算法的运行时是指对数据进行排序所需的比较次数或交换次数。这确实是一个很好的性能衡量标准，尤其是因为它独立于底层硬件设计。然而，其他事情——比如引用的局部性（即我们是否读取了大量可能在缓存中的元素？）——也在当前硬件上发挥着重要作用。特别是快速排序只需要很少的额外空间，并且表现出良好的缓存局部性，这使得它在许多情况下比合并排序更快。
此外，通过使用适当的枢轴选择，例如随机选择（这是一个很好的策略），几乎可以完全避免快速排序最坏的运行时间O（＜i＞n＜/i＞＜sup＞2＜/sup＞）。
在实践中，许多现代的快速排序实现（特别是libstdc++的std:：sort）实际上都是introsort，其理论上最坏情况是O（nlogn），与合并排序相同。它通过限制递归深度并切换到不同的算法（heapsort），一旦它超过logn。
问题回答
正如许多人所指出的，quicksort的平均案例性能比mergesort更快但是只有当您假设有恒定的时间按需访问任何内存时，这才是正确的。
在RAM中，这种假设通常不会太糟糕（由于缓存的原因，这种假设并不总是正确的，但也不会太糟糕）。然而，如果你的数据结构足够大，可以在磁盘上生存，那么quicksort会因为你的平均磁盘每秒进行200次随机搜索而被杀死。但同一个磁盘在按顺序读取或写入每秒兆字节的数据时没有问题。这正是mergesort所做的。
因此，如果必须在磁盘上对数据进行排序，那么您真的非常想在mergesort上使用一些变体。（一般情况下，您可以对子列表进行快速排序，然后在某个大小阈值以上开始将它们合并在一起。）
此外，如果您必须对这种大小的数据集执行任何操作，请认真考虑如何避免磁盘查找。例如，这就是为什么标准建议在数据库中加载大量数据之前先删除索引，然后再重建索引。在加载期间维护索引意味着不断地查找磁盘。相比之下，如果删除索引，那么数据库可以通过首先对要处理的信息进行排序（当然使用合并！），然后将其加载到索引的BTREE数据结构中来重建索引。（BTREE自然保持有序，因此您可以从排序后的数据集中加载一个，只需很少的磁盘搜索。）
在许多情况下，了解如何避免磁盘查找使我能够使数据处理工作耗时数小时，而不是数天或数周。
实际上，快速排序是O（n＜sup＞2＜/sup＞）。它的平均情况运行时间是O（nlog（n）），但其最坏情况O（n2），当您在包含很少唯一项的列表上运行它时，会发生这种情况。随机化需要O（n）。当然，这并不能改变最坏的情况，它只是防止恶意用户让你的排序花费很长时间。
快速排序更受欢迎，因为它：
- Is in-place (MergeSort requires extra memory linear to number of elements to be sorted).
- Has a small hidden constant.
“但大多数人使用Quicksort而不是Mergesort。为什么？”
一个尚未给出的心理学原因是Quicksort的名字更巧妙。即良好的营销。
是的，带有三部分的快速排序可能是最好的通用排序算法之一，但“快速”排序听起来比“合并”排序强大得多，这一事实不容忽视。
正如其他人所指出的，快速排序的最坏情况是O（n^2），而合并排序和堆排序则保持在O（nlogn）。然而，在平均情况下，这三种情况都是O（nlogn）；因此，它们在绝大多数情况下都具有可比性。
平均而言，Quicksort更好的地方在于，内部循环意味着将多个值与单个值进行比较，而在其他两个值上，每次比较的两个项都不同。换句话说，Quicksort的读取次数是其他两种算法的一半。在现代CPU上，访问时间在很大程度上决定了性能，因此最终Quicksort最终成为了一个不错的首选。
我想补充一点，在迄今为止提到的三种算法（mergesort、quicksort和heap sort）中，只有mergesort是稳定的。也就是说，对于那些具有相同键的值，顺序不会改变。在某些情况下，这是可取的。
但是，说实话，在实际情况下，大多数人只需要良好的平均性能，而快速排序是……快速=）
所有的排序算法都有起有落。请参阅维基百科关于排序算法的文章，以获得良好的概述。
我想在现有的好答案中添加一些关于快速排序在偏离最佳情况时如何执行以及这种情况的可能性有多大的数学计算，我希望这将帮助人们更好地理解为什么在更复杂的快速排序实现中，O（n^2）情况并不是真正的问题。
除了随机访问问题之外，还有两个主要因素会影响快速排序的性能，它们都与数据透视与正在排序的数据的比较有关。
1） 数据中的少量键。具有相同值的数据集将在n^2时间内在普通的两部分快速排序中排序，因为每次除了枢轴位置之外的所有值都放在一边。现代实现通过诸如使用三部分排序之类的方法来解决这一问题。这些方法在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% on one side: (ideal case)
- 75% on one side: 2.4 times as long
- 90% on one side: 6.6 times as long
- 95% on one side: 13.5 times as long
- 99% on one side: 69 times as long
当我们在一侧接近100%时，执行的对数部分接近n，整个执行渐近接近O（n^2）。
在QuickSort的初级实现中，排序数组（用于第一个元素枢轴）或反向排序数组（针对最后一个元素轴心）等情况将可靠地产生最坏情况下的O（n^2）执行时间。此外，具有可预测枢轴选择的实现可能会受到旨在产生最坏情况执行的数据的DoS攻击。现代实现通过多种方法来避免这种情况，例如在排序前对数据进行随机化，选择3个随机选择的索引的中值等。在混合中进行这种随机化，我们有2种情况：
- Small data set. Worst case is reasonably possible but O(n^2) is not catastrophic because n is small enough that n^2 is also small.
- Large data set. Worst case is possible in theory but not in practice.
我们看到糟糕表现的可能性有多大
机会微乎其微。让我们考虑一种5000个值：
我们假设的实现将使用3个随机选择的索引的中位数来选择一个枢轴。我们将认为在25%-75%范围内的枢轴是“好的”，而在0%-25%或75%-100%范围内的轴心是“坏的”。如果你使用3个随机索引的中位数来观察概率分布，那么每次递归都有11/16的机会以一个好的枢轴结束。让我们做两个保守（和错误）的假设来简化数学：
良好的枢轴总是精确地处于25%/75%的分割，并在2.4*的理想情况下运行。我们从来没有得到过理想的分割或任何比25/75更好的分割。
坏的枢轴总是最坏的情况，基本上对解决方案没有任何贡献。
我们的QuickSort实现将在n=10时停止，并切换到插入排序，因此我们需要22个25%/75%的透视分区来将5000值的输入分解到目前为止。（10*1.33333^22>；5000）或者，我们需要4990个最坏情况下的枢轴。请记住，如果我们在的任何点累积22个好的枢轴，那么排序就会完成，所以最坏的情况或任何接近它的情况都需要非常的坏运气。如果我们花了88次递归来实际实现排序到n=10所需的22个良好的枢轴，那么这将是4*2.4*的理想情况，或者大约是理想情况执行时间的10倍。在88次重复后，我们不实现所需的22个良好枢轴的可能性有多大？
二项式概率分布可以回答这个问题，答案大约是10^-18。（n是88，k是21，p是0.6875）您的用户在点击[SORT]所需的1秒内被闪电击中的可能性大约是他们看到5000项排序运行的可能性的一千倍，这比理想情况下的10*更糟糕。数据集越大，这种机会就越小。以下是一些数组大小及其相应的运行时间超过10*的机会：
- Array of 640 items: 10^-13 (requires 15 good pivot points out of 60 tries)
- Array of 5,000 items: 10^-18 (requires 22 good pivots out of 88 tries)
- Array of 40,000 items:10^-23 (requires 29 good pivots out of 116)
请记住，这是由两个比现实更糟糕的保守假设造成的。因此，实际性能更好，剩余概率的平衡更接近理想。
最后，正如其他人所提到的，如果递归堆栈太深，即使是这些不太可能的情况也可以通过切换到堆排序来消除。因此，TLDR是，对于QuickSort的良好实现，最坏的情况并不真正存在，因为它已经被设计出来，并且执行在O（n*logn）时间内完成。
这是采访中常见的一个问题，即尽管合并排序在最坏情况下的性能更好，但快速排序被认为比合并排序更好，尤其是对于大输入。由于某些原因，快速排序更好：
1-辅助空间：快速排序是一种就地排序算法。就地分拣意味着不需要额外的存储空间来执行分拣。另一方面，合并排序需要一个临时数组来合并已排序的数组，因此它不在适当的位置。
2-最坏情况：使用随机快速排序可以避免快速排序的最坏情况O（n^2）。通过选择正确的枢轴，可以很容易地以高概率避免这种情况。通过选择right pivot元素来获得平均事例行为，使其即兴发挥性能，并变得与Merge排序一样高效。
3-引用的局部性：Quicksort尤其表现出良好的缓存局部性，这使得它在许多情况下（如在虚拟内存环境中）比合并排序更快。
4-尾部递归：快速排序是尾部递归，而合并排序不是。尾部递归函数是指递归调用是函数执行的最后一件事的函数。尾部递归函数被认为比非尾部递归函数更好，因为编译器可以优化尾部递归。
来自快速排序上的维基百科条目：
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是实践中最快的排序算法，但有许多病理情况会使其表现与O（n2）一样糟糕。
堆排序保证在O（n*ln（n））中运行，并且只需要有限的额外存储。但有许多现实世界测试的引用表明，heapsort的平均速度明显慢于quicksort。
快速排序并不比合并排序好。对于O（n^2）（最坏的情况很少发生），快速排序可能比合并排序的O（nlogn）慢得多。快速排序的开销较小，因此对于较小的n和较慢的计算机，它更好。但今天的计算机速度如此之快，合并的额外开销可以忽略不计，而且在大多数情况下，非常缓慢的快速排序的风险远远超过合并的微不足道的开销。
此外，合并将具有相同键的项按其原始顺序保留，这是一个有用的属性。
为什么快速排序很好
- QuickSort takes N^2 in worst case and NlogN average case. The worst case occurs when data is sorted. This can be mitigated by random shuffle before sorting is started.
- QuickSort doesn t takes extra memory that is taken by merge sort.
- If the dataset is large and there are identical items, complexity of Quicksort reduces by using 3 way partition. More the no of identical items better the sort. If all items are identical, it sorts in linear time. [This is default implementation in most libraries]
快速排序总是比合并排序好吗
不是
- Mergesort is stable but Quicksort is not. So if you need stability in output, you would use Mergesort. Stability is required in many practical applications.
- Memory is cheap nowadays. So if extra memory used by Mergesort is not critical to your application, there is no harm in using Mergesort.
注意：在java中，Arrays.sort（）函数对基元数据类型使用Quicksort，对对象数据类型使用Mergesort。因为对象会消耗内存开销，所以从性能的角度来看，为Mergesort添加一点开销可能不会有任何问题。
参考：观看Coursera普林斯顿算法课程第3周
Unlike Merge Sort Quick Sort doesn t uses an auxilary space. Whereas Merge Sort uses an auxilary space O(n). But Merge Sort has the worst case time complexity of O(nlogn) whereas the worst case complexity of Quick Sort is O(n^2) which happens when the array is already is sorted.
答案会稍微倾向于快速排序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
关于DualPivot快速排序的更多精彩阅读-http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
在合并排序中，一般的算法是：
- Sort the left sub-array
- Sort the right sub-array
- Merge the 2 sorted sub-arrays
在顶层，合并2个排序的子数组需要处理N个元素。
低于此级别，步骤3的每次迭代都涉及处理N/2个元素，但您必须重复此过程两次。所以你仍然在处理2*N/2==N个元素。
在下面的一个级别上，您正在合并4*N/4==N个元素，依此类推。递归堆栈中的每个深度都涉及在该深度的所有调用中合并相同数量的元素。
请考虑快速排序算法：
- Pick a pivot point
- Place the pivot point at the correct place in the array, with all smaller elements to the left, and larger elements to the right
- Sort the left-subarray
- Sort the right-subarray
在顶层，您处理的是一个大小为N的数组。然后选择一个轴心点，将其放在正确的位置，然后可以在算法的其余部分完全忽略它。
在这一级别之下，您将处理两个子数组，它们的组合大小为N-1（即减去前面的轴心点）。您可以为每个子阵列拾取一个轴心点，最多可拾取2个额外的轴心点。
在这个级别之下的一个级别，您正在处理4个子阵列，其组合大小为N-3，原因与上面相同。
然后是N-7…然后是N-15…然后是N-32。。。
递归堆栈的深度保持大致相同（logN）。使用merge排序，您总是在递归堆栈的每个级别上处理N元素合并。不过，使用快速排序，处理的元素数量会随着堆栈的向下而减少。例如，如果您在递归堆栈的中途查看深度，则处理的元素数量为N-2^（（logN）/2））==N-sqrt（N）。
免责声明：在合并排序中，因为每次将数组划分为2个完全相等的块，所以递归深度正好是logN。在快速排序中，由于轴心点不太可能正好位于数组的中间，因此递归堆栈的深度可能略大于logN。我还没有做过数学计算，看看这个因素和上面描述的因素在算法的复杂性中到底扮演了多大的角色。
这是一个很老的问题，但由于我最近处理了这两个问题，下面是我的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%。
然而，如果您的（大）数组只有很少的唯一值，那么合并排序在任何情况下都会开始超过快速排序。
因此，也许底线是：如果比较很昂贵（例如，回调函数、比较字符串、比较结构的许多部分——大多数情况下都会使用第二个第三个第四个“if”来产生差异），那么合并排序可能会更好。对于更简单的任务，快速排序会更快。
That said all previously said is true: - Quicksort can be N^2, but Sedgewick claims that a good randomized implementation has more chances of a computer performing sort to be struck by a lightning than to go N^2 - Mergesort requires extra space
Quicksort具有更好的平均案例复杂性，但在某些应用程序中，这是错误的选择。Quicksort易受拒绝服务攻击。如果攻击者可以选择要排序的输入，他可以很容易地构造一个集，该集在最坏情况下具有o（n^2）的时间复杂性。
Mergessort的平均情况复杂度和最坏情况复杂度是相同的，因此不会遇到相同的问题。合并排序的这一特性也使其成为实时系统的最佳选择——正是因为没有病理病例会导致它运行得非常慢。
由于这些原因，我更喜欢Mergesort而不是Quicksort。
这很难说。MergeSort最差的是n（log2n）-n+1，如果n等于2^k，这是准确的（我已经证明了这一点）。对于任何n，它都在（n lg n-n+1）和（n lgn+n+O（lg n））之间。但对于quickSort，它最好的是nlog2n（n也等于2^k）。如果你用quickSort除以MergeSort，当n为无穷大时，它等于1。所以MergeSort的最坏情况似乎比QuickSort的最好情况好，为什么我们要使用快速排序？但请记住，MergeSort并没有到位，它需要2n的模因空间。而且MergeSort还需要做许多数组复制，我们在算法分析中不包括这些。总之，MergeSort在理论上确实比快速排序快，但实际上你需要考虑模因空间，数组复制的成本，合并比快速排序慢。我曾经做过一个实验，Random类给了我1000000个java数字，mergesort花了2610ms，quicksort花了1370ms。
快速排序是最坏的情况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。基于这种概率，快速排序对于平均（和典型）情况是有效的。
When I experimented with both sorting algorithms, by counting the number of recursive calls, quicksort consistently has less recursive calls than mergesort. It is because quicksort has pivots, and pivots are not included in the next recursive calls. That way quicksort can reach recursive base case more quicker than mergesort.
虽然它们都在同一个复杂度类中，但这并不意味着它们都有相同的运行时。Quicksort通常比mergesort更快，因为它更容易编写紧凑的实现，而且它所做的操作可以更快。这是因为快速排序通常更快，所以人们使用它而不是合并排序。
然而我个人经常会使用mergesort或quicksort变体，当quicksort表现不佳时，它会降级为mergesort。回想起快速排序在平均上仅为O（n log n）。最坏的情况是O（n^2）！合并排序总是O（n log n）。如果必须具有实时性能或响应能力，并且输入数据可能来自恶意来源，则不应使用普通快速排序
在所有条件相同的情况下，我希望大多数人使用最方便的东西，这往往是qsort（3）。除此之外，已知快速排序在数组上非常快，就像合并排序是列表的常见选择一样。
我想知道的是，为什么很少看到基数或bucket排序。它们是O（n），至少在链表上是这样，所需要的只是将键转换为序数的某种方法。（字符串和浮点运算很好。）
我认为原因与计算机科学的教学方式有关。我甚至不得不向我的算法分析讲师证明，排序确实有可能比O（n log（n））更快。（他有证据表明，你可以比O（n log（n））更快地进行t比较排序，这是真的。）
在其他新闻中，浮点可以按整数排序，但之后必须将负数翻转过来。
Edit: Actually, here s an even more vicious way to sort floats-as-integers: http://www.stereopsis.com/radix.html. Note that the bit-flipping trick can be used regardless of what sorting algorithm you actually use...
快速排序与合并排序的小添加。
它也可能取决于排序项目的种类。如果访问项、交换和比较不是简单的操作，比如比较平面内存中的整数，那么合并排序可能是更可取的算法。
例如，我们在远程服务器上使用网络协议对项目进行排序。
Also, in custom containers like "linked list", the are no benefit of quick sort.
1. Merge sort on linked list, don t need additional memory.
2. Access to elements in quick sort is not sequential (in memory)
快速排序是一种就地排序算法，因此它更适合数组。另一方面，合并排序需要额外的O（N）存储空间，更适合于链表。
与数组不同，在liked列表中，我们可以在中间插入项目，并使用O（1）空间和O（1”时间，因此可以在没有任何额外空间的情况下实现合并排序中的合并操作。然而，为数组分配和取消分配额外空间会对合并排序的运行时间产生不利影响。合并排序也有利于链表，因为数据是按顺序访问的，没有太多随机内存访问。
另一方面，快速排序需要大量的随机内存访问，使用数组，我们可以直接访问内存，而无需按照链表的要求进行任何遍历。此外，当用于数组时，快速排序具有良好的引用位置，因为数组连续存储在内存中。
尽管两种排序算法的平均复杂度都是O（NlogN），但通常执行普通任务的人会使用数组进行存储，因此快速排序应该是首选算法。
编辑：我刚刚发现合并排序最坏/最佳/平均情况总是nlogn，但快速排序可以从n2（元素已经排序时的最坏情况）到nlogn（pivot总是将数组一分为二时的平均/最佳情况）不等。
Consider time and space complexity both. For Merge sort : Time complexity : O(nlogn) , Space complexity : O(nlogn)
For Quick sort : Time complexity : O(n^2) , Space complexity : O(n)
Now, they both win in one scenerio each. But, using a random pivot you can almost always reduce Time complexity of Quick sort to O(nlogn).
因此，在许多应用程序中，快速排序是首选，而不是合并排序。
In c/c++ land, when not using stl containers, I tend to use quicksort, because it is built into the run time, while mergesort is not.
所以我相信，在许多情况下，这只是阻力最小的路径。
此外，对于整个数据集不适合工作集的情况，使用快速排序可以获得更高的性能。
相关问题
热门标签
- winforms
- combobox
- fogbugz
- java
- date
- internationalization
- asp.net
- iis
- url-rewriting
- urlrewriter
- c#
- enums
- ocaml
- haxe
- algorithm
- string
- viewstate
- .net
- c++
- c
- symbol-table
- mysql
- database
- postgresql
- licensing
- migration
- vb.net
- vb6
- declaration
- vb6-migration
- python
- psycopg2
- backup
- vmware
- virtualization
- gnu-screen
- authentication
- desktop
- excel
- xll
- cultureinfo
- regioninfo
- oracle
- client
- session
- download
- html
- virtual
- constructor
- scenarios
- perl
- full-text-search
- javascript
- ajax
- testing
- oop
- inheritance
- vim
- encapsulation
- information-hiding