为什么quicksort的平均速度比其他人快？

Question

我们知道,快速排序性能平均为O(n*log(n)),但合并和堆性能平均也是O(n*log(n)).所以问题是为什么quicksort的平均速度更快.

Answer 1

维基百科建议:

通常,快速排序在实践中比其他O(nlogn)算法快得多,因为它的内循环可以在大多数架构上有效地实现,并且在大多数现实世界的数据中,可以做出设计选择,以最小化需要二次方的概率.时间.此外,quicksort倾向于充分利用内存层次结构,充分利用虚拟内存和可用缓存.虽然quicksort不是就地排序并使用辅助内存,但它非常适合现代计算机体系结构.

还要看一下与同一页面上的其他排序算法的比较.

另请参见为什么quicksort在实践中比其他排序算法更好？在CS网站上.

Answer 2

快速排序的最坏情况实际上比堆排序和归并排序更糟糕，但平均而言，快速排序更快。

至于为什么，需要时间解释，因此我将参考Skiena，算法设计手册。

总结快速排序与合并/堆排序的引用：

当面对相同渐进复杂度的算法时，实现细节和系统特性（例如缓存性能和内存大小）很可能被证明是决定性因素。我们可以说的是，实验表明，在正确实施的快速排序实施得很好的情况下，它通常比归并排序或堆排序快 2-3 倍。主要原因是最内层循环中的操作更简单。但是，如果您不相信我说快速排序更快，我无法与您争论。这是一个问题的解决方案超出了我们正在使用的分析工具。最好的判断方法是实现算法和实验。