快速排序的最坏情况性能为 O(n 2 )，但无论如何在实践中仍然广泛使用。为什么是这样？
halovi
问问题
8868 次
8 回答
25
你不应该只关注最坏的情况，只关注时间复杂度。它更多的是关于平均而不是最差，它是关于时间和空间的。
快速排序：
- 平均时间复杂度为 Θ( n log n )；
- 可以用 Θ(log n ) 的空间复杂度来实现；
还要考虑到大 O 表示法不考虑任何常数，但在实践中，如果算法快几倍，它确实会有所不同。Θ( n log n ) 表示，该算法在K n log( n ) 中执行，其中K是常数。快速排序是具有最低K的比较排序算法。
于 2009-04-21T10:06:47.863 回答
7
QuickSort 的平均渐近顺序是O(nlogn)并且由于较小的常数（更紧密的循环），它通常比堆排序更有效。事实上，有一个理论上的线性时间中值选择算法，您可以使用它来始终找到最佳枢轴，从而产生最坏的情况O(nlogn)。然而，普通的快速排序通常比这个理论上的快。
为使其更合理，请考虑 QuickSort 将在 中完成的概率。这只是意味着它几乎永远不会遇到那种糟糕的情况。O(n2)1/n!
于 2009-04-21T09:57:09.680 回答
6
有趣的是，快速排序平均比合并排序执行更多的比较——快速排序为 1.44 n lg n（预期），而合并排序为 n lg n。如果重要的是比较，那么合并排序将比快速排序更可取。
快速排序快速的原因是它具有许多其他理想的属性，这些属性在现代硬件上运行得非常好。例如，快速排序不需要动态分配。它可以在原始数组上就地工作，仅使用 O(log n) 堆栈空间（如果实施正确，最坏的情况）来存储递归所需的堆栈帧。尽管可以使用合并排序来执行此操作，但这样做通常会在合并步骤期间导致巨大的性能损失。其他排序算法（如堆排序）也具有此属性。
此外，快速排序具有出色的参考位置。分区步骤，如果使用 Hoare 的就地分区算法完成，本质上是从阵列两端向内执行的两次线性扫描。这意味着快速排序将有非常少量的缓存未命中，这在现代架构上对性能至关重要。另一方面，堆排序没有很好的局部性（它在整个数组中跳跃），尽管大多数合并排序实现具有合理的局部性。
快速排序也非常可并行化。一旦进行了初始分区步骤以将数组拆分为越来越小的区域，这两个部分就可以相互独立地进行排序。许多排序算法可以并行化，包括归并排序，但由于上述原因，并行快速排序的性能往往优于其他并行算法。另一方面，堆排序没有。
快速排序的唯一问题是它可能会降级到 O(n 2 )，这在大型数据集上可能非常严重。避免这种情况的一种方法是让算法自省，并在退化的情况下切换到速度较慢但更可靠的算法之一。该算法称为introsort，是一种出色的混合排序算法，它在没有病态情况的情况下获得了快速排序的许多好处。
总之：
- 除了递归中使用的堆栈帧外，快速排序是就地的，它占用 O(log n) 空间。
- 快速排序具有良好的参考局部性。
- 快速排序很容易并行化。
这解释了为什么快速排序往往优于纸面上可能更好的排序算法。
希望这可以帮助！
于 2013-01-15T23:48:12.277 回答
1
因为平均而言，它是最快的比较排序（就经过时间而言）。
于 2009-04-21T09:56:44.017 回答
1
因为，在一般情况下，它是最快的排序算法之一。
于 2009-04-21T09:56:55.670 回答
1
不过，除了最快之外，还可以通过在对数组进行排序之前对其进行洗牌来避免其中的一些不良情况。至于小数据集的弱点，显然不是一个大问题，因为数据集很小，排序时间可能也很短。
例如，我为快速排序和冒泡排序编写了一个 python 函数。冒泡排序需要大约 20 秒来对 10,000 条记录进行排序，7500 条记录需要 11 秒，5000 条记录需要 5 秒。快速排序在大约 0.15 秒内完成所有这些排序！
于 2013-01-15T21:38:37.420 回答
0
可能值得指出的是，C 确实具有库函数qsort()，但并不要求使用实际的 QuickSort 来实现它，这取决于编译器供应商。
于 2009-04-21T10:08:57.967 回答
0
Bcs 这是一种算法，在 O(NlogN) 复杂度的大型数据集上运行良好。这也是占用恒定空间的就地算法。通过明智地选择枢轴元素，我们可以避免更糟糕的快速排序情况，并且即使在排序后的数组上也总是会在 O(NlogN) 中执行。
于 2013-01-20T11:33:37.917 回答