快速排序具有更好的平均情况复杂度，但在某些应用中它是错误的选择。快速排序容易受到拒绝服务攻击。如果攻击者可以选择要排序的输入，他可以很容易地构造一个时间复杂度为o(n^2)的最坏情况的集合。

归并排序的平均情况复杂性和最坏情况复杂性是相同的，因此不会遇到相同的问题。归并排序的这一特性也使它成为实时系统的最佳选择——确切地说，因为没有导致它运行得非常非常慢的病理情况。

由于这些原因，我更喜欢归并排序，而不是快速排序。

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

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

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

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

1 Sedgewick，算法

在所有条件相同的情况下，我希望大多数人使用最方便的方法，这往往是qsort(3)。除此之外，快速排序在数组上非常快，就像归并排序是列表的常用选择一样。

我想知道的是为什么基数排序和桶排序这么少见。它们是O(n)至少在链表上是这样的它所需要的只是将键转换为序数的方法。(字符串和浮动工作得很好。)

我认为原因与计算机科学的教学方式有关。我甚至不得不向我的讲师演示算法分析，它确实有可能比O(nlog (n))更快地排序。(他证明了比较排序不能比O(nlog (n))快，这是正确的)

在其他新闻中，浮点数可以按整数排序，但之后必须将负数反转。

编辑: 实际上，这里有一种更糟糕的将浮点数作为整数排序的方法:http://www.stereopsis.com/radix.html。注意，不管你实际使用什么排序算法，比特翻转技巧都可以使用……

同时考虑时间和空间的复杂性。 归并排序: 时间复杂度: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 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.)