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

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

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

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

1 Sedgewick，算法

在c/c++领域，当不使用stl容器时，我倾向于使用快速排序，因为它是构建的 进入运行时，而归并排序没有。

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

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

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

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

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

而且，在像“链表”这样的自定义容器中，也没有快速排序的好处。 1. 对链表进行归并排序，不需要额外的内存。 2. 快速排序中对元素的访问不是顺序的(在内存中)

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

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

1) A small number of keys in the data. A dataset of all the same value will sort in n^2 time on a vanilla 2-partition QuickSort because all of the values except the pivot location are placed on one side each time. Modern implementations address this by methods such as using a 3-partition sort. These methods execute on a dataset of all the same value in O(n) time. So using such an implementation means that an input with a small number of keys actually improves performance time and is no longer a concern.

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²)。

In a naive implementation of QuickSort, cases such as a sorted array (for 1st element pivot) or a reverse-sorted array (for last element pivot) will reliably produce a worst-case O(n^2) execution time. Additionally, implementations with a predictable pivot selection can be subjected to DoS attack by data that is designed to produce worst case execution. Modern implementations avoid this by a variety of methods, such as randomizing the data before sort, choosing the median of 3 randomly chosen indexes, etc. With this randomization in the mix, we have 2 cases:

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

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

这种可能性微乎其微。让我们考虑5000个值:

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

好的枢轴总是精确地在25%/75%的分割和2.4*理想情况下运行。我们从来没有得到过理想的分割或者比25/75更好的分割。 糟糕的枢轴总是最坏的情况，基本上对解决方案没有任何贡献。

Our QuickSort implementation will stop at n=10 and switch to an insertion sort, so we require 22 25%/75% pivot partitions to break the 5,000 value input down that far. (10*1.333333^22 > 5000) Or, we require 4990 worst case pivots. Keep in mind that if we accumulate 22 good pivots at any point then the sort will complete, so worst case or anything near it requires extremely bad luck. If it took us 88 recursions to actually achieve the 22 good pivots required to sort down to n=10, that would be 4*2.4*ideal case or about 10 times the execution time of the ideal case. How likely is it that we would not achieve the required 22 good pivots after 88 recursions?

二项概率分布可以回答这个问题，答案是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)时间内完成。

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

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

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

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

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

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

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

所有排序算法都有其起伏。有关排序算法的概述，请参阅维基百科的文章。