我想在现有的优秀答案中添加一些关于快速排序在偏离最佳情况时的表现以及这种情况的可能性的数学，我希望这将帮助人们更好地理解为什么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)时间内完成。

One of the reason is more philosophical. Quicksort is Top->Down philosophy. With n elements to sort, there are n! possibilities. With 2 partitions of m & n-m which are mutually exclusive, the number of possibilities go down in several orders of magnitude. m! * (n-m)! is smaller by several orders than n! alone. imagine 5! vs 3! *2!. 5! has 10 times more possibilities than 2 partitions of 2 & 3 each . and extrapolate to 1 million factorial vs 900K!*100K! vs. So instead of worrying about establishing any order within a range or a partition,just establish order at a broader level in partitions and reduce the possibilities within a partition. Any order established earlier within a range will be disturbed later if the partitions themselves are not mutually exclusive.

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

Quick Sort is like Managerial approach where one is not initially concerned about any order , only about meeting a broad criterion with No regard for order. Then the partitions are narrowed until you get a sorted set. The real challenge in Quicksort is in finding a partition or criterion in the dark when you know nothing about the elements to sort. That is why we either need to spend some effort to find a median value or pick 1 at random or some arbitrary "Managerial" approach . To find a perfect median can take significant amount of effort and leads to a stupid bottom up approach again. So Quicksort says just a pick a random pivot and hope that it will be somewhere in the middle or do some work to find median of 3 , 5 or something more to find a better median but do not plan to be perfect & don't waste any time in initially ordering. That seems to do well if you are lucky or sometimes degrades to n^2 when you don't get a median but just take a chance. Any way data is random. right. So I agree more with the top ->down logical approach of quicksort & it turns out that the chance it takes about pivot selection & comparisons that it saves earlier seems to work better more times than any meticulous & thorough stable bottom ->up approach like merge sort. But

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

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

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

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

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

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

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

That's hard to say.The worst of MergeSort is n(log2n)-n+1,which is accurate if n equals 2^k(I have already proved this).And for any n,it's between (n lg n - n + 1) and (n lg n + n + O(lg n)).But for quickSort,its best is nlog2n(also n equals 2^k).If you divide Mergesort by quickSort,it equals one when n is infinite.So it's as if the worst case of MergeSort is better than the best case of QuickSort,why do we use quicksort?But remember,MergeSort is not in place,it require 2n memeroy space.And MergeSort also need to do many array copies,which we don't include in the analysis of algorithm.In a word,MergeSort is really faseter than quicksort in theroy,but in reality you need to consider memeory space,the cost of array copy,merger is slower than quick sort.I once made an experiment where I was given 1000000 digits in java by Random class,and it took 2610ms by mergesort,1370ms by quicksort.