6个回答
17
通常取决于所涉及的数据结构。快速排序通常是最快的，但不能保证 O(n*log(n))；在某些退化情况下，它会变成 O(n^2)。堆排序是通常的替代方案；它保证了 O(n*log(n))，无论初始顺序如何，但其常数因子要高得多。当您需要一个时间上限时，通常会使用它。一些更近期的算法使用快速排序，但尝试识别何时开始退化，然后转换为堆排序。如果数据结构不支持随机访问，则使用归并排序，因为它使用纯顺序访问（前向迭代器而不是随机访问迭代器）。例如，在
std::list<>::sort中使用它。它也广泛用于外部排序，其中与顺序访问相比，随机访问可能非常昂贵。（在对不适合放入内存的文件进行排序时，您可以将其分成适合放入内存的块，使用快速排序对这些块进行排序，将每个块写入文件，然后 对生成的文件进行归并排序。）- James Kanze
5
1很有趣...这是一个面试问题...该公司的文件系统主要使用顺序访问（仅追加而不重写）...我现在可以理解为什么他们会问这个问题以及它与什么相关。 - user656925
你的意思是说，当数据结构不支持随机访问时，使用归并排序...也就是说，你必须迭代才能获取所需的值？ - user656925
@ChrisAaker 我的意思是你不能便宜地去到数据集中的任意位置。归并排序最初是设计用于磁带上的。即使在磁盘文件上，相对于顺序读取，随机定位到文件中的任意位置相对较昂贵。当然，在标准库中，前向和双向迭代器不支持加法；你需要一个随机访问迭代器来实现。 （而
std::list具有双向迭代器，因此std::sort无法使用它。） - James Kanze这应该是被接受的答案。我会考虑一些关于稳定性的因素（快速排序通常不在高效实现之列），但你发布了一个很好的概述。+1 - Marco A.
如果你需要对链表进行排序，归并排序也是一个不错的选择。 - Cameron
11
归并排序在处理链表时更快。这是因为合并列表时指针可以很容易地改变。它只需要一次遍历（O(n)）整个列表。
快速排序的原地算法需要移动（交换）数据。虽然这对于内存中的数据集非常高效，但如果您的数据集不适合内存，则可能会更加昂贵。结果将是大量的I/O。
这些天，有很多并行化发生。并行化Mergesort比快速排序（原地）简单。如果不使用原地算法，则quicksort的空间复杂度为O(n)，与mergesort相同。
因此，总的来说，快速排序可能更适用于适合内存的数据集。对于更大的数据集，最好使用归并排序。
另一个选择归并排序而不是快速排序的时间是，如果数据非常相似（即不接近均匀）。快速排序依赖于使用枢轴。如果所有值都类似，则快速排序达到O（n ^ 2）的最坏情况。如果数据的值非常相似，则更有可能选择一个不良的枢轴，导致非常不平衡的分区，从而导致O（n ^ 2）运行时。最直观的例子是如果列表中的所有值都相同。
- pschang
5
在两个算法中，如果你需要一个稳定的排序，使用归并排序。如果不需要，可以使用修改后的快速排序（如introsort），因为它往往更快且使用的内存更少。
Hoare所描述的普通快速排序对于会导致性能下降的特殊情况非常敏感，使其成为Theta(n^2)，因此通常需要使用修改版。这就是数据分布的作用，因为归并排序没有坏的情况。一旦开始修改快速排序，您可以进行各种不同的调整，而introsort是其中更有效的一种。它可以即时检测是否处于糟糕情况，并在必要时切换到堆排序。
事实上，Hoare最基本的快速排序对于已经排序好的数据效果最差，因此您的“好测试用例”在某种程度上会使其性能下降。然而，这只是出于好奇，因为避免这种情况只需要非常小的调整，根本不需要像introsort那样复杂。因此，分析受已排序数据影响的版本是过于简单化的。
在实践中，在C++中，通常会使用std::stable_sort和std::sort而不必过于担心确切的算法。
Hoare所描述的普通快速排序对于会导致性能下降的特殊情况非常敏感，使其成为Theta(n^2)，因此通常需要使用修改版。这就是数据分布的作用，因为归并排序没有坏的情况。一旦开始修改快速排序，您可以进行各种不同的调整，而introsort是其中更有效的一种。它可以即时检测是否处于糟糕情况，并在必要时切换到堆排序。
事实上，Hoare最基本的快速排序对于已经排序好的数据效果最差，因此您的“好测试用例”在某种程度上会使其性能下降。然而，这只是出于好奇，因为避免这种情况只需要非常小的调整，根本不需要像introsort那样复杂。因此，分析受已排序数据影响的版本是过于简单化的。
在实践中，在C++中，通常会使用std::stable_sort和std::sort而不必过于担心确切的算法。
- Steve Jessop
3
你有任何性能下降的特殊情况示例吗？ - user656925
我记得读过一些关于快速排序的注意事项，如果用户提供特别制作的数据，快速排序将表现出最坏情况，基本上会导致DOS攻击。尽管我还没有看到任何这种情况会成为真正问题的情况。@ChrisAaker iirc快速排序的原始版本使用第一个元素作为枢轴，所以这很容易创建。对于更复杂的变体（首个、最后一个、中间），它几乎不可能偶然发生。 - Voo
Voo所说的，我认为有一些论文构建了至少对于中值三数枢轴选择的杀手，甚至可能是更好的枢轴选择。然而，如果你非常关心DOS攻击，那么随机枢轴选择可以打败所有精心制作的输入，而且坏情况发生的概率非常低，以至于对于任何足够大的输入数据，你都会关心自己是否处于一个糟糕的情况中。这在“可忽略”的意义上是如此，即“你更有可能遭受宇宙射线位翻转或行星的自发爆炸”。 - Steve Jessop
5
虽然Java 6及更早版本使用归并排序算法进行排序，但C#使用快速排序算法。
尽管它们都是O(nlogn)的时间复杂度，但快速排序比归并排序表现更好。快速排序的常数比归并排序小。
- DarthVader
7
常数更小...即在大O表示法中被移除的常数？ - user656925
除非在极少数情况下出现，否则归并排序和堆排序都是O(nlog(n))。快速排序的最佳情况是O(nlog(n))，但最坏情况是O(n^2)。 - James Kanze
最坏情况是数据按相反顺序排序。这会导致O(n**2)的运行时间。但通常不会出现这种情况。在大多数情况下，除非数据按相反顺序排序，否则快速排序的性能优于归并排序。 - DarthVader
你的意思是“除非它是按相反顺序排序”...基本上当数据按相反顺序排序时...快速排序会降至最坏情况的大O(n*n)。 - user656925
如果您从中间选择枢轴元素，则快速排序对于已排序的列表和“反向排序”的输入都是O(log n)。 - fredoverflow
显示剩余2条评论
1
在实践中，请记住，除非您有一个非常大的数据集并且/或者执行排序很多次，否则这可能根本不重要。话虽如此，快速排序通常被认为是“最快”的n*log(n)排序器。请参阅已经提出的这个问题：快速排序与归并排序
- Peter
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
std::sort...始终如此 :) - avakarO(N^2)），则会回退到归并排序。 - David Rodríguez - dribeas