同时考虑时间和空间的复杂性。 归并排序: 时间复杂度:O(nlogn)， 空间复杂度:O(nlogn)

快速排序: 时间复杂度:O(n²)， 空间复杂度:O(n)

现在，他们各自在一个场景中获胜。 但是，使用随机枢轴，您几乎总是可以将快速排序的时间复杂度降低到O(nlogn)。

因此，在许多应用中，快速排序是首选，而不是归并排序。

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

为什么快速排序很好?

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使用的额外内存对您的应用程序不是至关重要的，那么使用Mergesort也没有什么害处。

注意:在java中，Arrays.sort()函数对基本数据类型使用快速排序，对对象数据类型使用归并排序。因为对象消耗内存开销，所以为归并排序增加一点开销对于性能来说可能不是什么问题。

参考:在Coursera上观看普林斯顿算法课程第三周的快速排序视频

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

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

同时考虑时间和空间的复杂性。 归并排序: 时间复杂度:O(nlogn)， 空间复杂度:O(nlogn)

快速排序: 时间复杂度:O(n²)， 空间复杂度:O(n)

现在，他们各自在一个场景中获胜。 但是，使用随机枢轴，您几乎总是可以将快速排序的时间复杂度降低到O(nlogn)。

因此，在许多应用中，快速排序是首选，而不是归并排序。

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

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

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

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

1 Sedgewick，算法