algorithm - 为什么快速排序比归并排序好？

Question

我在面试时被问到这个问题。它们都是 O(nlogn)，但大多数人使用 Quicksort 而不是 Mergesort。这是为什么？

Answer 1

Quicksort 有 O(n²) 最坏情况运行时间和 O(nlogn) 平均案例运行时。然而，它在许多情况下优于归并排序，因为许多因素会影响算法的运行时间，并且当将所有因素放在一起时，快速排序会胜出。

特别是，经常引用的排序算法的运行时间是指对数据进行排序所需的比较次数或交换次数。这确实是一个很好的性能衡量标准，尤其是因为它独立于底层硬件设计。然而，其他事情——比如引用的位置(即我们是否读取了很多可能在缓存中的元素？)——也在当前的硬件上发挥着重要作用。尤其是快速排序需要很少的额外空间并表现出良好的缓存局部性，这使得它在许多情况下比归并排序更快。

此外，通过使用适当的枢轴选择，几乎可以完全避免快速排序的 O(n²) 最坏情况运行时间 – 例如随机挑选它(这是一个很好的策略)。

在实践中，许多现代的快速排序实现(特别是 libstdc++ 的 std::sort)实际上是 introsort ，其理论上的最坏情况是 O(nlogn)，与归并排序相同。它通过限制递归深度并在超过 logn 时切换到不同的算法 (heapsort) 来实现这一点。