在堆排序快速排序的优势 [英] Quicksort superiority over Heap Sort

问题描述

堆排序有最坏情况复杂度为O（n日志）N wnile快速排序为O（n ^ 2）。 但emperical证据说，快速排序优越。这是为什么呢？

Heap Sort has a worst case complexity is O(nlog) n wnile Quicksort is 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屋！