Mal*_*har 351 language-agnostic sorting algorithm mergesort quicksort
我在接受采访时被问到这个问题.他们都是O(nlogn),但大多数人使用Quicksort而不是Mergesort.这是为什么？
use*_*318 284
正如许多人所指出的,快速排序的平均案例性能比mergesort快. 但是,如果您假设有时间按需访问任何内存,则情况才是正确的.
在RAM中,这个假设通常不是太糟糕(因为缓存并不总是如此,但它并不太糟糕).但是,如果您的数据结构足够大,可以存放在磁盘上,那么快速排序会因为您的平均磁盘每秒执行200次随机搜索而被杀死.但是同一个磁盘在顺序读取或写入每秒兆字节的数据方面没有问题.这正是mergesort的作用.
因此,如果必须在磁盘上对数据进行排序,那么您真的非常希望在mergesort上使用一些变体.(通常,您会快速排序子列表,然后开始将它们合并到一些大小阈值之上.)
此外,如果您必须对该大小的数据集执行任何操作,请仔细考虑如何避免寻找磁盘.例如,这就是为什么在数据库中执行大量数据加载之前删除索引的标准建议,然后再重建索引.在加载期间维护索引意味着不断寻求磁盘.相比之下,如果删除索引,那么数据库可以通过首先对要处理的信息进行排序(当然使用mergesort!)然后将其加载到索引的BTREE数据结构中来重建索引.(BTREE自然是按顺序保存的,因此您可以从排序的数据集中加载一个,只需很少的搜索到磁盘.)
在很多情况下,理解如何避免磁盘搜索让我使数据处理工作需要数小时而不是数天或数周.
Kon*_*lph 264
Quicksort具有O(n 2)最坏情况运行时和O(n log n)平均情况运行时.但是,它在许多场景中优于合并排序,因为许多因素会影响算法的运行时间,并且当将它们全部放在一起时,快速排序会胜出.
特别地,经常引用的排序算法运行时指的是执行排序数据所需的比较次数或交换次数.这确实是衡量性能的一个很好的指标,特别是因为它独立于底层硬件设计.但是,其他的东西 - 比如引用的位置(即我们读了很多可能在缓存中的元素？) - 在当前的硬件上也扮演着重要的角色.Quicksort特别需要很少的额外空间并且具有良好的缓存局部性,这使得它在许多情况下比合并排序更快.
此外,通过使用适当的枢轴选择 - 例如随机选择它(这是一个很好的策略),很容易避免快速排序的O(n 2)的最坏情况运行时间.
在实践中,许多现代的quicksort实现(特别是libstdc ++ std::sort)实际上都是introsort,其理论最坏情况是O(n log n),与merge sort相同.它通过限制递归深度来实现这一点,并且一旦超过log n就切换到不同的算法(heapsort).
Dar*_*ari 89
实际上,QuickSort是O(n 2).它的平均案例运行时间是O(nlog(n)),但最坏的情况是O(n 2),当你在包含很少的唯一项目的列表上运行它时会发生.随机化需要O(n).当然,这并没有改变它最糟糕的情况,它只是防止恶意用户花费很长时间进行排序.
QuickSort更受欢迎,因为它:
Ash*_*Ash 29
"然而大多数人使用Quicksort而不是Mergesort.为什么会这样？"
没有给出的一个心理原因就是Quicksort更加巧妙地命名.即良好的营销.
是的,具有三重分区的Quicksort可能是最好的通用排序算法之一,但是没有克服"快速"排序听起来比"合并"排序更强大的事实.
Jav*_*ier 16
正如其他人所说,Quicksort的最坏情况是O(n ^ 2),而mergesort和heapsort留在O(nlogn).然而,在一般情况下,所有三个都是O(nlogn); 所以他们对绝大多数情况都具有可比性.
使Quicksort平均更好的原因是内循环意味着将几个值与单个值进行比较,而另外两个值对于每个比较都是不同的.换句话说,Quicksort读取的数量是其他两种算法的一半.在现代CPU上,性能主要受访问时间的影响,因此最终Quicksort成为首选.
Him*_*sal 11
这是采访中常见的问题，尽管合并排序在最坏情况下性能更好，但快速排序被认为比合并排序更好，特别是对于大输入。由于某些原因，快速排序更好：
1-辅助空间：快速排序是一种就地排序算法。就地排序意味着不需要额外的存储空间来执行排序。另一方面，合并排序需要一个临时数组来合并已排序的数组，因此它不是就地排序。
2-最坏情况：O(n^2)通过使用随机快速排序可以避免快速排序的最坏情况。通过选择正确的枢轴，可以很容易地以高概率避免这种情况。通过选择正确的主元元素来获得平均情况行为，可以提高性能并变得与合并排序一样高效。
3-引用局部性：快速排序尤其表现出良好的缓存局部性，这使得它在许多情况下（例如在虚拟内存环境中）比合并排序更快。
4-尾递归：快速排序是尾递归，而合并排序不是。尾递归函数是递归调用是函数执行的最后一件事的函数。尾递归函数被认为比非尾递归函数更好，因为尾递归可以由编译器优化。
我想补充到目前为止提到的三个算法(mergesort,quicksort和heap sort),只有mergesort是稳定的.也就是说,对于具有相同键的那些值,顺序不会改变.在某些情况下,这是可取的.
但是,说实话,在实际情况下,大多数人只需要良好的平均表现,快速排序就是......快=)
所有排序算法都有其起伏.有关排序算法的信息,请参阅Wikipedia文章以获得良好的概
Quicksort还与mergesort竞争,这是另一种递归排序算法,但具有最坏情况Θ(nlogn)运行时间的好处.Mergesort是一种稳定的类型,与quicksort和heapsort不同,可以很容易地适应在链接列表和存储在缓慢访问介质(如磁盘存储或网络附加存储)上的非常大的列表上运行.尽管可以编写快速排序以在链接列表上操作,但是它通常会在没有随机访问的情况下遭受不良的数据透视选择.mergesort的主要缺点是,当在数组上操作时,它在最佳情况下需要Θ(n)辅助空间,而具有就地分区和尾递归的快速排序的变体仅使用Θ(logn)空间.(请注意,在链接列表上操作时,mergesort只需要一小块恒定的辅助存储空间.)
Quicksort是实践中最快的排序算法,但有许多病理案例可以使它的表现与O(n2)一样糟糕.
保证Heapsort在O(n*ln(n))中运行,并且只需要有限的额外存储空间.但是现实世界测试有许多引用表明,heapsort平均比快速排序明显慢.
快速排序并不比合并排序更好。对于 O(n^2)（很少发生的最坏情况），快速排序可能比合并排序的 O(nlogn) 慢得多。快速排序的开销较小，因此对于较小的 n 和较慢的计算机来说，它更好。但是今天的计算机速度如此之快，以至于合并排序的额外开销可以忽略不计，并且在大多数情况下，非常慢的快速排序的风险远远超过合并排序的微不足道的开销。
此外，合并排序会按照原始顺序留下具有相同键的项目，这是一个有用的属性。
小智 6
我想在现有的很好的答案中添加一些关于 QuickSort 在偏离最佳情况时的表现以及可能性有多大的数学，我希望这将帮助人们更好地理解为什么 O(n^2) 情况不是真实的关注更复杂的 QuickSort 实现。
除了随机访问问题之外，还有两个主要因素会影响 QuickSort 的性能，它们都与数据透视与排序数据的比较方式有关。
1）数据中的少量键。所有相同值的数据集将在普通 2 分区 QuickSort 上按 n^2 次排序，因为每次除枢轴位置外的所有值都放在一侧。现代实现通过使用 3 分区排序等方法解决了这个问题。这些方法在 O(n) 时间内在所有相同值的数据集上执行。所以使用这样的实现意味着具有少量键的输入实际上提高了性能时间并且不再是一个问题。
2) 极差的枢轴选择会导致最坏情况下的性能。在理想情况下，枢轴始终是 50% 的数据较小，50% 的数据较大，因此在每次迭代中输入将被分成两半。这给了我们 n 次比较和交换时间为 O(n*logn) 时间的 log-2(n) 递归。
非理想的枢轴选择对执行时间有多大影响？
让我们考虑这样一种情况，即始终选择枢轴使得 75% 的数据位于枢轴的一侧。它仍然是 O(n*logn) 但现在日志的基数已更改为 1/0.75 或 1.33。更改基数时的性能关系始终是由 log(2)/log(newBase) 表示的常量。在这种情况下，该常数为 2.4。因此，这种枢轴选择的质量比理想的要长 2.4 倍。
这种情况恶化的速度有多快？
不是很快，直到枢轴选择变得（始终）非常糟糕：
当我们在一侧接近 100% 时，执行的日志部分接近 n，整个执行渐近地接近 O(n^2)。
在 QuickSort 的简单实现中，排序数组（对于第一个元素主元）或反向排序数组（对于最后一个元素主元）等情况将可靠地产生最坏情况 O(n^2) 的执行时间。此外，具有可预测枢轴选择的实现可能会受到旨在产生最坏情况执行的数据的 DoS 攻击。现代实现通过多种方法避免这种情况，例如在排序前随机化数据，选择 3 个随机选择的索引的中位数等。 混合使用这种随机化，我们有两种情况：
我们看到糟糕表现的可能性有多大？
机会微乎其微。让我们考虑一种 5,000 个值：
我们的假设实现将使用 3 个随机选择的索引的中位数来选择一个枢轴。我们会将 25%-75% 范围内的支点视为“好”，将 0%-25% 或 75%-100% 范围内的支点视为“坏”。如果您使用 3 个随机索引的中位数查看概率分布，则每次递归都有 11/16 的机会以良好的支点结束。让我们做 2 个保守的（和错误的）假设来简化数学：
良好的支点总是恰好在 25%/75% 的分割，并在 2.4*理想情况下运行。我们永远不会得到理想的分割或任何比 25/75 更好的分割。
坏的支点总是最坏的情况，基本上对解决方案没有任何帮助。
我们的 QuickSort 实现将在 n=10 处停止并切换到插入排序，因此我们需要 22 个 25%/75% 的主元分区来将 5,000 值输入分解到那么远。(10*1.333333^22 > 5000) 或者，我们需要 4990 个最坏情况枢轴。请记住，如果我们在任何时候积累了 22 个良好的支点，那么排序就会完成，因此最坏的情况或接近它的任何情况都需要非常糟糕的运气。如果我们用了 88 次递归来实际实现排序到 n=10 所需的 22 个好的枢轴，那将是 4*2.4*理想情况或理想情况下执行时间的大约 10 倍。在 88 次递归之后，我们无法实现所需的 22 个良好支点的可能性有多大？
二项式概率分布可以回答这个问题，答案大约是 10^-18。（n 为 88，k 为 21，p 为 0.6875）您的用户在单击 [SORT] 所需的 1 秒内被闪电击中的可能性比他们看到 5,000 项排序运行情况更糟的可能性高出大约 1000 倍比 10*理想情况。这个机会随着数据集变大而变小。以下是一些数组大小及其运行时间超过 10*ideal 的相应机会：
请记住，这是两个比现实更糟糕的保守假设。所以实际表现要好一些，剩余概率的平衡也比较接近理想。
最后，正如其他人所提到的，如果递归堆栈太深，即使是这些非常不可能的情况也可以通过切换到堆排序来消除。所以 TLDR 是，对于 QuickSort 的良好实现，最坏的情况并不真正存在，因为它已经被设计出来并且执行在 O(n*logn) 时间内完成。