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

Question

根据我的计算:

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

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

Answer 1

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

您确实可以表明，平均而言，快速排序比堆排序进行更多的比较(快速排序大约 1.44 n log₂ n 与 n log₂ n 与堆排序相比)。然而，比较并不是堆排序和快速排序运行时的唯一决定因素。

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

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

此外，请注意 log(nⁿ) = n log n 和 log (n!) = n log n - n + O(log n) 通过 Stirling's approximation .这意味着 log (n!) 并不比 n log n 小很多，即使 n 变得非常大。肯定有区别，但它还不足以自行产生巨大的凹痕。

希望这对您有所帮助!