堆排序缺点何在?

最近在看coursera上的算法课,里面讲堆排序那集,最后提到,heap sort “make poor use of cache memory". 想了一下不太懂。他好像是拿堆排序跟快速排序作对比地说。 链接 : Algorithms, Part I 最后面他的解释,不甚明白。 为什么比快排 make poor use of cache memory?
关注者
100
被浏览
13665

4 个回答

(谢谢邀请)
平均时间上,堆排序的时间常数比快排要大一些,因此通常会慢一些,但是堆排序最差时间也是O(nlogn)的,这点比快排好。
关于 poor use of cache memory,我的理解是快排在递归进行部分的排序的时候,只会访问局部的数据,因此缓存能够更大概率的命中;而堆排序的建堆过程是整个数组各个位置都访问到的,后面则是所有未排序数据各个位置都可能访问到的,所以不利于缓存发挥作用。简答的说就是快排的存取模型的局部性(locality)更强,堆排序差一些。
我理解,速度和缓存的问题都反映了堆排序让数据过于大距离的移动,你观察某个元素在整个排序过程中的移动过程,会发现它是前后大幅度的跑动;而快速排序则是尽快的移动到最终的位置,然后做小范围的跳动。
下面是10个随机数进行快速排序和堆排序的过程,你可以盯着某个元素往下看,会发现堆排序中,一些元素在左右乱跳,而快速排序中这样的情况会少很多。(数据产生的 Go 源代码在这里: Path of quick-sort and heap sort.
Data  {9 4 2 6 8 0 3 1 7 5}
Index [0 1 2 3 4 5 6 7 8 9]

Quick-sort
[[0 1 2 3 4 5 6 7 8 9]
 [9 1 2 3 4 5 6 7 8 0]
 [9 1 2 7 4 5 6 3 8 0]
 [9 1 2 7 6 5 4 3 8 0]
 [5 1 2 7 6 9 4 3 8 0]
 [5 1 2 7 6 9 3 4 8 0]
 [5 1 2 7 6 9 3 8 4 0]
 [5 2 1 7 6 9 3 8 4 0]
 [5 2 7 1 6 9 3 8 4 0]
 [5 7 2 1 6 9 3 8 4 0]
 [5 7 2 6 1 9 3 8 4 0]](11x10)

Heap-sort
[[0 1 2 3 4 5 6 7 8 9]
 [0 1 2 8 4 5 6 7 3 9]
 [0 1 6 8 4 5 2 7 3 9]
 [0 4 6 8 1 5 2 7 3 9]
 [0 4 6 8 9 5 2 7 3 1]
 [1 4 6 8 9 5 2 7 3 0]
 [4 1 6 8 9 5 2 7 3 0]
 [4 8 6 1 9 5 2 7 3 0]
 [4 8 6 3 9 5 2 7 1 0]
 [1 8 6 3 9 5 2 7 4 0]
 [8 1 6 3 9 5 2 7 4 0]
 [8 3 6 1 9 5 2 7 4 0]
 [7 3 6 1 9 5 2 8 4 0]
 [3 7 6 1 9 5 2 8 4 0]
 [3 9 6 1 7 5 2 8 4 0]
 [2 9 6 1 7 5 3 8 4 0]
 [9 2 6 1 7 5 3 8 4 0]
 [9 1 6 2 7 5 3 8 4 0]
 [5 1 6 2 7 9 3 8 4 0]
 [1 5 6 2 7 9 3 8 4 0]
 [1 2 6 5 7 9 3 8 4 0]
 [7 2 6 5 1 9 3 8 4 0]
 [6 2 7 5 1 9 3 8 4 0]
 [5 2 7 6 1 9 3 8 4 0]
 [2 5 7 6 1 9 3 8 4 0]
 [7 5 2 6 1 9 3 8 4 0]
 [5 7 2 6 1 9 3 8 4 0]](27x10)
关于cache locality,如果愿意看c++的话可以看这个:
m.youtube.com/watch?
简言之快排是顺着扫的,堆排序是跳着走的。

快排比堆排序快还有个原因,就是平均情况下堆排序更接近n lg n,而快排要好些。详见这篇:
数学之美番外篇:快排为什么那样快