5

根据我的计算：

  • 快速排序成本 = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ... = n * log(n) = log(n n )
  • 堆排序成本 = sum [log(i)] for i = n, n-1, n-2, ..., 1 = log(n!)

为什么说快速排序比堆排序具有更好的常数因子，因此快速排序平均优于堆排序？不是 log(n n ) > log(n!) 吗？

4

2 回答 2

11

我认为这里的问题是您对快速排序和堆排序的分析不够精确，无法说明为什么常数因子会有所不同。

您确实可以证明，平均而言，快速排序将比堆排序进行更多的比较（快速排序大约为 1.44 n log 2 n 与 n log 2 n 与堆排序）。但是，比较并不是堆排序和快速排序运行时的唯一决定因素。

快速排序更快的主要原因是引用的局部性。 由于内存缓存的工作方式，相邻位置的数组访问往往比分散在整个数组中的数组访问快得多。在快速排序中，分区步骤通常在数组的末端进行所有读取和写入，因此数组访问彼此紧密排列。另一方面，堆排序在数组上下移动时会在数组周围跳跃。因此，平均而言，快速排序中的数组访问比堆排序中的数组访问花费的时间要少得多。差异足够大，以至于快速排序中 n log n 项前面的常数因子低于堆排序中 n log n 项前面的常数因子，这就是快速排序比堆排序快得多的原因之一。

简而言之 - 如果我们只关心比较，那么堆排序是比快速排序更好的选择。但是由于内存系统使用缓存并且缓存未命中成本很高，因此快速排序通常是更好的选择。

另外，请注意 log(n n ) = n log n 和 log (n!) = n log n - n + O(log n) 通过斯特林近似。这意味着 log (n!) 并不比 n log n 小很多，即使 n 变得非常大。肯定有区别，但它还不足以单独造成巨大的影响。

希望这可以帮助！

于 2013-08-27T00:05:39.560 回答
6

以下是 Steven S. Skiena 的《算法设计手册》中的段落，其中谈到了三种 O(nlogn) 排序算法之间的速度：

但是我们如何比较两个 Θ(n log n) 算法来决定哪个更快？我们如何证明快速排序真的很快？不幸 的是，RAM 模型和 Big Oh 分析提供了一组过于粗糙的工具，无法做出这种区分。当面对具有相同渐近复杂度的算法时，实现细节和系统怪癖（例如缓存性能和内存大小）很可能被证明是决定性因素。

我们可以说的是，实验表明，在正确实现快速排序的情况下，它通常比合并排序或堆排序快 2-3 倍。主要原因是最内层循环中的操作更简单。但是，当我说快速排序更快时，如果您不相信我，我无法与您争论。 这个问题的解决方案超出了我们正在使用的分析工具。最好的判断方法是实现算法和实验。

-4.6.3 《快速排序真的快吗？》，算法设计手册

于 2013-08-27T01:11:41.377 回答