为什么快速排序的常数因子比堆排序好？

Question

根据我的计算：

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

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

- user389955

---

“Cost” 可以有很多含义。你是在谈论最坏情况下的比较次数吗？ - user395760

为什么使用数学软件Mathematica标签？ - arshajii

请参阅《算法导论》了解为什么堆排序的时间复杂度为O(n log n)。 - Oliver Charlesworth

@delnan：意味着时间复杂度。 - user389955

因为堆排序的声誉不佳。请参见http://www.azillionmonkeys.com/qed/sort.html - harold

Answer 1

我认为问题在于你对快速排序和堆排序的分析不够精确，无法展示常数因子之间的差异。

确实，你可以证明平均而言，快速排序比堆排序做更多比较操作（大约是快速排序的 1.44 n log₂ n 次比较操作，而堆排序是 n log₂ n 次）。但是，比较操作并不是影响堆排序和快速排序运行时间的唯一因素。

快速排序更快的主要原因是“局部性原理” 。由于内存缓存的工作方式，相邻位置的数组访问通常比散布在整个数组中的访问要快得多。在快速排序中，划分步骤通常在数组的两端进行所有读写操作，因此数组访问紧密相邻。另一方面，堆排序在向上或向下移动堆时会在数组中跳来跳去。因此，平均而言，快速排序中的数组访问要比堆排序中的数组访问快得多。这种差异足够大，以至于快速排序中n log n 项前面的常数因子比堆排序中的更小，这就是快速排序比堆排序更快的原因之一。

简单地说-如果我们只关心比较操作，那么堆排序比快速排序更好。但由于内存系统使用缓存，缓存未命中很昂贵，通常情况下快速排序是更好的选择。

另外，注意 log(nⁿ) = n log n 和 log (n!) = n log n - n + O(log n) ，通过斯特林逼近可得。这意味着当 n 很大时，log (n!) 与 n log n 的差别并不太大。肯定存在差异，但单独这点差异还不足以产生巨大影响。

希望这能帮到你！

- templatetypedef

---

我的信息摘要：1）常数因子的确定不仅取决于理论比较，还取决于实现细节。Qsort具有小的常数因子，因为它对缓存友好。对于Qsort：下一个要访问的元素通常在内存中靠近刚刚查看的元素。对于Hsort，访问需要上下跳跃... - user389955

@templatetypdef: 感谢您提供如此详细和有用的解释。像您这样的人，使stackoverflow变得越来越受欢迎。 - user389955

我相信你在这里混淆了归并排序和堆排序。当通过堆进行冒泡时，必须将可能的两个父节点相互比较以找到较小的父节点，然后将其与正在冒泡的节点进行比较，以确定是否要冒泡。这是对log_2级别的2次比较，使得它成为2 n log_2（n）比较，这比快速排序更糟糕。相比之下，使用归并排序，每次比较都会将某些内容上移一个log_2（n）级别，导致n log_2（n），这比快速排序更好。 - btilly

Answer 2

以下是Steven S. Skiena的《算法设计手册》中关于三种O(nlogn)排序算法速度比较的段落：

但是，我们如何比较两个Θ(n log n)算法以决定哪个更快？我们如何证明快速排序确实很快？不幸的是，RAM模型和大O分析提供了太粗略的工具集来进行这种区分。在面对相同渐进复杂度的算法时，实现细节和系统怪癖，例如缓存性能和内存大小，可能会成为决定性因素。

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

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

- vvy