为什么快速排序比归并排序更好？

Question

为什么快速排序比归并排序更好？

algorithmsortinglanguage-agnosticquicksortmergesort

408

面试时有人问了我这个问题。它们都是O(nlogn)的，但大多数人使用快速排序而不是归并排序。为什么呢？

- Xardas

105

这不是一个很好的面试问题。现实世界中的数据并不是随机排列的：它通常包含有很多顺序，而聪明的排序算法可以利用这些顺序，虽然两种算法都不能自动地做到这一点，但更容易将归并排序修改成具有这种功能，而快速排序则较难。GNU libc的qsort、Python的list.sort以及Firefox JavaScript中的Array.prototype.sort都是强化版的归并排序。（GNU STL的sort使用Introsort，但这可能是因为在C++中，交换操作可能比复制操作更加高效。） - Jason Orendorff

5

为什么“修改归并排序使其实现此目的比修改快速排序更容易”？您可以引用任何具体示例吗？ - Lazer

17

合并排序（Merge Sort）是通过将初始数据分组成有序的子数组来开始的。如果数组最初包含一些已经排序好的区域，那么在开始之前检测到它们可以节省大量时间。而且你可以在O(n)的时间内完成这项工作。有关具体示例，请参见我提到的三个项目的源代码！最好的例子可能是Python的Timsort算法，在此处详细描述：http://svn.python.org/view/python/trunk/Objects/listsort.txt?view=markup 并在http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup 中实现。 - Jason Orendorff

5

不确定我是否同意你的观点，即归并排序更容易修改以利用已排序的部分。快速排序的分区步骤可以轻松修改为在分区后检查两个结果分区是否已排序，如果是，则停止递归。这可能会使比较次数翻倍，但不会改变该步骤的O(n)时间复杂度。 - j_random_hacker

4

@j_random_hacker: 对的，这就是我的意思。但请考虑一下：{10, 2, 3, 4, 5, 6, 7, 8, 1, 9}，尽管已经几乎完全排序，但在分区之前和之后都不会找到它，在后续调用检查之前，分区会破坏它。与此同时，归并排序在移动任何元素之前就会在分割步骤中检查已排序的序列，而聪明的算法将特别在分割步骤中寻找像这样的运行序列（参见：Tim排序）。 - Mooing Duck

显示剩余5条评论

29个回答

310

正如许多人所指出的，快速排序的平均情况性能比归并排序更快。但是，这只有在假定可以随时访问任何内存部分的时间保持不变的情况下才成立。

在RAM中，这种假设通常还不错（由于缓存的存在，它不总是正确的，但也不算太糟糕）。但是，如果您的数据结构足够大以存储在磁盘上，则快速排序会因为平均硬盘每秒执行大约200个随机寻道的事实而受到影响。但是，同样的硬盘可以毫不费力地按顺序读取或写入每秒兆字节级别的数据。这正是归并排序所做的。

因此，如果必须在磁盘上对数据进行排序，则确实需要使用归并排序的某种变体。（通常，您会将子列表快速排序，然后在某些大小阈值以上开始将它们合并在一起。）

此外，如果您必须处理那么大的数据集，要好好考虑如何避免寻道磁盘。例如，这就是为什么在数据库中进行大规模数据加载之前，请删除索引，然后再重新构建索引的标准建议。在加载过程中维护索引意味着不断寻道到磁盘。相反，如果您删除索引，则数据库可以通过首先对要处理的信息进行排序（当然使用归并排序！）然后将其加载到BTREE数据结构以用于索引来重新构建索引。（BTREE自然保持有序，因此您可以从已排序的数据集中加载它并减少到磁盘的寻道次数。）

有许多场合，了解如何避免磁盘寻道使我能够使数据处理作业从需要数天甚至数周缩短为数小时。

- user11318

1

非常好，没有考虑访问数据结构所做的假设。很有洞察力 :) - chutsu

2

你能解释一下“磁盘查找”是什么意思吗？它是否意味着在数据存储在磁盘上时搜索某个单一值？ - James Wierzba

10

从上下文中我理解他的意思是“寻找磁盘上的某个位置”。在旋转磁盘设备上，“寻道”指的是将读头抬起并移动到新的绝对地址，这是一个非常慢的操作。当您按存储顺序访问数据时，磁盘硬件无需寻道，只需顺序读取项目并以高速运行即可。 - nclark

1

有人可以再详细解释一下吗？我这样理解快速排序：如果我们选择随机的枢轴，调用栈会将数组分为随机的片段。这需要随机访问。然而，对于栈中的每个调用，左右指针都会顺序移动。我假设这些指针会被保留在缓存中。交换操作也是在缓存中进行的（最终写入磁盘）。 - sam

1

只是一点贡献，避免昂贵的磁盘读写开销：当对需要磁盘访问的非常大的数据进行排序时，将每次排序的方向切换是有优势的。也就是说，在循环的最顶层，第一次从0到n，下一次从n到0。这带来了撤退（排序）已经在内存（缓存）中可用的数据块的优势，并且仅需一次磁盘访问攻击两次。我认为大多数DBMS都使用这种优化技术。 - ssd

显示剩余4条评论

100

实际上，快速排序的时间复杂度为O(n²)。它的平均运行时间是O(nlog(n)), 但其最坏情况是O(n²)，当你对包含少量唯一项的列表进行排序时会出现最坏情况。随机化需要O(n)的时间。当然，这不会改变它的最坏情况，只是防止恶意用户使您的排序花费很长时间。

相比之下，快速排序更受欢迎的原因是：

是就地排序（归并排序需要额外的内存，与要排序的元素数量成正比）。
具有较小的隐藏常量。

- Dark Shikari

6

实际上，有一些快速排序的实现在最坏情况下时间复杂度为O(n*log(n))，而不是O(n^2)。 - jfs

15

这也取决于计算机架构。快速排序受缓存的好处，而归并排序则不受其影响。 - Cristian Ciupitu

5

很可能这些是introsort实现而不是quicksort（introsort最初是quicksort，如果它即将停止成为n*log(n)，则切换到heapsort）。 - CesarB

51

你可以在原地实现归并排序。 - Marcin

8

归并排序可以实现只需要 O(1) 的额外存储空间，但是大多数这样实现的方法在性能方面都有很大的缺陷。 - Clearer

显示剩余20条评论

37

"为什么大多数人使用Quicksort而不是Mergesort呢？"

一个未被提到的心理原因是Quicksort的名称更加巧妙，也就是说它有很好的市场营销。

是的，使用三路快排的Quicksort可能是最好的通用排序算法之一，但无法否认的事实是，“Quick”排序听起来比“Merge”排序更加强大。

- Ash

14

不回答哪一个更好的问题。算法的名称与确定哪一个更好无关。 - Nick Gallimore

1

没有人因使用快速排序而被解雇。 - Code Whisperer

23

正如其他人所指出的，快速排序的最坏情况时间复杂度为O(n^2)，而归并排序和堆排序则保持在O(nlogn)。然而，在平均情况下，这三种算法都是O(nlogn)的；因此，它们在绝大多数情况下是可以相互比较的。

使得快速排序平均更好的原因是其内部循环涉及将多个值与单个值进行比较，而在另外两种算法中，每次比较都涉及到不同的两个术语。换句话说，快速排序只需读取其他两个算法的一半数据。在现代CPU上，性能主要受访问时间的影响，因此最终快速排序成为了一个很好的首选。

- Javier

10

这是一个常见的问题，即使合并排序的最坏情况性能比快速排序好，但特别是对于大型输入，快速排序仍被认为比合并排序更好。以下是某些原因，使得快速排序更好：

1- 辅助空间：快速排序是一种原地排序算法。原地排序意味着执行排序不需要额外的存储空间。另一方面，合并排序需要临时数组来合并已排序数组，因此它不是原地排序。

2- 最坏情况：通过使用随机化快速排序可以避免快速排序的最坏情况O(n^2)。通过选择正确的枢轴元素，可以很容易地高概率避免这种情况。选择正确的枢轴元素使其获得平均情况行为，从而提高了性能，并变得与合并排序一样有效。

3- 引用局部性：快速排序特别表现出良好的缓存局部性，在虚拟内存环境中这使得它比合并排序更快。

4- 尾递归：快速排序是尾递归，而合并排序不是。尾递归函数是指递归调用是函数执行的最后一件事情的函数。尾递归函数比非尾递归函数更好，因为编译器可以对尾递归进行优化。

- Himanshu Kansal

喜欢这个答案 - 谢谢！简明扼要。如果有任何更正或修改，请留言评论。 - rinogo

（在第二点中可能值得提到，“三个随机数的中位数”方法似乎可以防止大多数情况下的O(n^2)时间复杂度） - rinogo

一些使用辅助空间的归并排序版本——如果想保留原始列表但同时也需要一个指向元素的排序列表，这并不是问题，而且这些版本并不递归。此外，在对文件进行排序时，所需的RAM量可能非常小。 - supercat

9

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

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

所有排序算法都有其优缺点。请参阅维基百科排序算法文章以获得良好的概述。

- Antti Rasinen

8

我希望能够在现有的优秀答案基础上，添加一些关于快速排序在最佳情况下和偏离最佳情况时的数学知识，以及这种情况发生的可能性。我希望这些知识可以帮助人们更好地理解为什么在更复杂的快速排序实现中，O(n^2)的情况并不是真正需要担心的问题。

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

1）数据中键值数量很少。在普通的双向划分快速排序算法中，如果数据集中所有值都相同，则会在n^2时间内进行排序，因为每次都将除了枢轴位置之外的所有值放在一侧。现代实现方法通过使用三向排序等方法来解决这个问题。这些方法可以在O(n)时间内对所有值相同的数据集进行排序。因此，使用这样的实现意味着输入具有少量键值实际上可以提高性能，并且不再是一个问题。

2) 极差的主元选择可能导致最坏情况的性能。在理想情况下，主元将始终是这样的：50％的数据较小，50％的数据较大，以便在每次迭代期间将输入拆分成两半。这给我们n比较和交换乘以log-2（n）递归，时间复杂度为O（n * logn）。

非理想主元选择对执行时间有多大影响？

让我们考虑一种情况，其中主元被一致地选择，以使75％的数据位于主元的一侧。它仍然是O（n * logn），但现在log的底数已更改为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%时，执行的对数部分趋近于n，并且整个执行渐近地趋向于O(n^2)。

在快速排序的朴素实现中，像一个有序数组（以第一个元素为枢轴）或反向排序的数组（以最后一个元素为枢轴）这样的情况将可靠地产生最坏情况下的O(n^2)执行时间。此外，具有可预测的枢轴选择的实现可以受到旨在产生最坏情况执行的数据的DoS攻击。现代实现通过各种方法来避免这种情况，例如在排序之前随机化数据，选择3个随机选择的索引的中位数等。在这种随机化混合的情况下，我们有两种情况：

对于小的数据集，最坏情况发生的可能性比较大，但由于n足够小，n^2也很小，因此O(n^2)并不是灾难性的。
对于大的数据集，最坏情况在理论上可能出现，但实际上不会。

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

机会是微乎其微的。让我们考虑一个包含5,000个值的排序：

我们假设的实现将使用三个随机选择的索引的中位数来选择枢轴。我们将认为处于25% -75%范围内的枢轴是“好”的，而处于0％-25％或75％-100％范围内的枢轴是“坏”的。如果您查看使用三个随机索引的中位数的概率分布，每次递归都有11/16的几率最终得到一个好的枢轴。为了简化计算，让我们进行两个保守（错误的）假设：

好的轴点总是恰好在25%/75%的分割处，并以2.4倍的理想情况运作。我们从未得到过理想的分割或任何比25/75更好的分割。
坏的轴点总是最坏情况，并且基本上对解决方案没有贡献。

我们的快速排序实现将在n = 10时停止并切换到插入排序，因此我们需要22个25%/75%的轴点分区来将5000个值的输入拆分到那么深的程度。(10 * 1.333333 ^ 22> 5000) 或者，我们需要4990个最坏情况的轴点。请记住，如果我们在任何时候积累了22个好的轴点，则排序将完成，因此最坏情况或接近最坏情况需要非常糟糕的运气。如果我们实际上需要88次递归才能达到22个好的轴点来排序到n = 10，那将是4 * 2.4倍的理想情况，大约是理想情况的10倍执行时间。在88次递归后仍无法获得所需的22个好的轴点的可能性有多大？

二项式概率分布可以回答这个问题，答案约为10^-18。(n为88，k为21，p为0.6875) 在点击[排序]所需的1秒钟内，用户被雷击的可能性是看到5000个项目排序运行比10 *理想情况更糟糕的可能性的千倍左右。随着数据集变大，这种可能性会变得更小。以下是一些数组大小及其对应的长时间运行超过10 *理想的机会：

640个项目的数组：10^-13（需要在60次尝试中获得15个良好的枢轴点）
5000个项目的数组：10^-18（需要在88次尝试中获得22个良好的枢轴点）
40000个项目的数组：10^-23（需要在116次尝试中获得29个良好的枢轴点）

请记住，这是基于比实际情况更差的两个保守假设。因此，实际表现要更好，剩余概率的平衡更接近理想情况。

最后，正如其他人所提到的，如果递归栈过深，甚至这些极不可能的情况也可以通过切换到堆排序来消除。因此，简而言之，对于好的快速排序实现来说，最坏情况实际上并不存在，因为它已经被设计出来，并且执行时间为O(n*logn)。

- Lance Wisely

2

现有的优秀答案是哪些？我找不到它们。 - Jim Balter

快速排序的任何变体是否通知比较函数有关分区的信息，以便允许利用在分区中所有项目的大部分密钥都相同的情况？ - supercat

如果快速排序使用任何确定性伪随机方法来选择枢轴，那么可以有人故意排列数据，以产生最坏情况的性能，需要对其进行排序的列表将受到影响。 - supercat

8

Mu! 快速排序并不比归并排序更好，它适用于与归并排序不同类型的应用。

如果速度至关重要，不能容忍糟糕的最坏情况性能，并且有额外的空间可用，那么值得考虑使用归并排序。1

你说过它们“都是O(nlogn)”……这是错误的。“在最坏情况下，快速排序使用约n^2/2次比较。”1。

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

1 Sedgewick, Algorithms

- Roman Glass

归并排序可以原地实现，因此不需要额外的空间。例如，使用双向链表：https://dev59.com/p3A85IYBdhLWcg3wHvo0#6065792 - lanoxx

7

从维基百科关于快速排序的条目：

快速排序和归并排序是两种递归排序算法，但归并排序具有最坏情况Θ(nlogn)运行时间的优点。与快速排序和堆排序不同，归并排序是一种稳定排序，并且可以轻松地适应于操作链接列表和存储在慢速访问媒体（如磁盘存储或网络附加存储）上的非常大的列表。虽然快速排序可以编写为操作链接列表，但如果没有随机访问，它通常会遭受糟糕的枢轴选择。归并排序的主要缺点是，在操作数组时，它在最佳情况下需要Θ(n)的辅助空间，而使用原位分区和尾递归的快速排序变体仅使用Θ(logn)的空间。（请注意，在操作链接列表时，归并排序仅需要少量的常量辅助存储器。）

- gnobal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Konrad Rudolph · Accepted Answer

快速排序的最坏运行时间为O(n²)，平均情况下的运行时间为O(nlogn)。然而，在许多情况下，它比归并排序更优秀，因为许多因素会影响算法的运行时间，综合考虑，快速排序胜出。

特别是，经常引用的排序算法运行时间是指执行数据排序所需的比较次数或交换次数。这确实是一个很好的性能指标，尤其是它不受底层硬件设计的影响。但是，其他因素（如参考局部性 - 即我们读取的元素是否在缓存中？）也在当前硬件上发挥着重要作用。快速排序特别需要很少的额外空间，并且表现出良好的高速缓存局部性，这使其在许多情况下比归并排序更快。

此外，通过使用适当的枢轴选择（例如随机选择），可以很容易地几乎完全避免快速排序的最坏情况运行时间O(n²)。

实际上，许多现代快速排序的实现（特别是libstdc++的std::sort）实际上是introsort，其理论最坏情况与归并排序相同为O(nlogn)。通过限制递归深度，并在超过logn时切换到另一种算法（heapsort），它实现了这一点。