快速排序优于堆排序 [英] Quicksort superiority over Heap Sort

问题描述

堆排序的最坏情况复杂度为O(nlogn)，而快速排序的复杂度为O(n^2).但经验证据表明，快速排序更胜一筹.这是为什么?

Heap Sort has a worst case complexity of O(nlogn) while Quicksort has O(n^2). But emperical evidences say quicksort is superior. Why is that?

推荐答案

主要因素之一是快速排序具有更好的引用局部性 -- 下一个要访问的东西通常在内存中很近到你刚才看的东西.相比之下，堆排序跳得更多.由于靠近的事物可能会被缓存在一起，因此快速排序往往会更快.

One of the major factors is that quicksort has better locality of reference -- the next thing to be accessed is usually close in memory to the thing you just looked at. By contrast, heapsort jumps around significantly more. Since things that are close together will likely be cached together, quicksort tends to be faster.

然而，快速排序的最坏情况性能明显比堆排序差.由于某些关键应用程序需要保证速度性能，因此堆排序是处理此类情况的正确方法.

However, quicksort's worst-case performance is significantly worse than heapsort's is. Because some critical applications will require guarantees of speed performance, heapsort is the right way to go for such cases.

这篇关于快速排序优于堆排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！