堆排序缺点何在？如何理解快速排序的效率高于归并排序、堆排序

最近在看coursera上的算法课，里面讲堆排序那集，最后提到，heap sort “make poor use of cache memory". 想了①下不太懂。他好像是拿堆排序跟快速排序作对比地说。

链接 ： Algorithms, Part I

最后面他的解释，不甚明白。 为什么比快排 make poor use of cache memory？

（谢谢邀请）

平均时间上，堆排序的时间常数比快排要大①些，因此通常会慢①些，但是堆排序最差时间也是O(nlogn)的，这点比快排好。

关于 poor use of cache memory，我的理解是快排在递归进行部分的排序的时候，只会访问局部的数据，因此缓存能够更大概率的命中；而堆排序的建堆过程是整个数组各个位置都访问到的，后面则是所有未排序数据各个位置都可能访问到的，所以不利于缓存发挥作用。简答的说就是快排的存取模型的局部性（locality）更强，堆排序差①些。

我理解，速度和缓存的问题都反映了堆排序让数据过于大距离的移动，你观察某个元素在整个排序过程中的移动过程，会发现它是前后大幅度的跑动；而快速排序则是尽快的移动到最终的位置，然后做小范围的跳动。

下面是①⓪个随机数进行快速排序和堆排序的过程，你可以盯着某个元素往下看，会发现堆排序中，①些元素在左右乱跳，而快速排序中这样的情况会少很多。（数据产生的 Go 源代码在这里： Path of quick-sort and heap sort.）

Data {⑨ ④ ② ⑥ ⑧ ⓪ ③ ① ⑦ ⑤}Index [⓪ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨]Quick-sort[[⓪ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨] [⑨ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⓪] [⑨ ① ② ⑦ ④ ⑤ ⑥ ③ ⑧ ⓪] [⑨ ① ② ⑦ ⑥ ⑤ ④ ③ ⑧ ⓪] [⑤ ① ② ⑦ ⑥ ⑨ ④ ③ ⑧ ⓪] [⑤ ① ② ⑦ ⑥ ⑨ ③ ④ ⑧ ⓪] [⑤ ① ② ⑦ ⑥ ⑨ ③ ⑧ ④ ⓪] [⑤ ② ① ⑦ ⑥ ⑨ ③ ⑧ ④ ⓪] [⑤ ② ⑦ ① ⑥ ⑨ ③ ⑧ ④ ⓪] [⑤ ⑦ ② ① ⑥ ⑨ ③ ⑧ ④ ⓪] [⑤ ⑦ ② ⑥ ① ⑨ ③ ⑧ ④ ⓪]](①①x①⓪)Heap-sort[[⓪ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨] [⓪ ① ② ⑧ ④ ⑤ ⑥ ⑦ ③ ⑨] [⓪ ① ⑥ ⑧ ④ ⑤ ② ⑦ ③ ⑨] [⓪ ④ ⑥ ⑧ ① ⑤ ② ⑦ ③ ⑨] [⓪ ④ ⑥ ⑧ ⑨ ⑤ ② ⑦ ③ ①] [① ④ ⑥ ⑧ ⑨ ⑤ ② ⑦ ③ ⓪] [④ ① ⑥ ⑧ ⑨ ⑤ ② ⑦ ③ ⓪] [④ ⑧ ⑥ ① ⑨ ⑤ ② ⑦ ③ ⓪] [④ ⑧ ⑥ ③ ⑨ ⑤ ② ⑦ ① ⓪] [① ⑧ ⑥ ③ ⑨ ⑤ ② ⑦ ④ ⓪] [⑧ ① ⑥ ③ ⑨ ⑤ ② ⑦ ④ ⓪] [⑧ ③ ⑥ ① ⑨ ⑤ ② ⑦ ④ ⓪] [⑦ ③ ⑥ ① ⑨ ⑤ ② ⑧ ④ ⓪] [③ ⑦ ⑥ ① ⑨ ⑤ ② ⑧ ④ ⓪] [③ ⑨ ⑥ ① ⑦ ⑤ ② ⑧ ④ ⓪] [② ⑨ ⑥ ① ⑦ ⑤ ③ ⑧ ④ ⓪] [⑨ ② ⑥ ① ⑦ ⑤ ③ ⑧ ④ ⓪] [⑨ ① ⑥ ② ⑦ ⑤ ③ ⑧ ④ ⓪] [⑤ ① ⑥ ② ⑦ ⑨ ③ ⑧ ④ ⓪] [① ⑤ ⑥ ② ⑦ ⑨ ③ ⑧ ④ ⓪] [① ② ⑥ ⑤ ⑦ ⑨ ③ ⑧ ④ ⓪] [⑦ ② ⑥ ⑤ ① ⑨ ③ ⑧ ④ ⓪] [⑥ ② ⑦ ⑤ ① ⑨ ③ ⑧ ④ ⓪] [⑤ ② ⑦ ⑥ ① ⑨ ③ ⑧ ④ ⓪] [② ⑤ ⑦ ⑥ ① ⑨ ③ ⑧ ④ ⓪] [⑦ ⑤ ② ⑥ ① ⑨ ③ ⑧ ④ ⓪] [⑤ ⑦ ② ⑥ ① ⑨ ③ ⑧ ④ ⓪]](②⑦x①⓪)

快排数据越无序越快（加入随机化后基本不会退化），平均常数最小，不需要额外空间，不稳定排序。

归排速度稳定，常数比快排略大，需要额外空间（还有个东西叫多路归并），稳定排序。

堆排序传说中数据量越大排序越快……个人没有测到让他比快排还快的数据量。不过（据说）因为堆排的交换时候的寻址花时间比另外两个排序时间长，所以常数最大。实际测出来它相对最慢。不需要额外空间，不稳定排序。

按需求选择排序吧 ……

快排应该是最佳的通用排序算法！

快排代码紧凑，常数因子小，局部性良好！

归并需要额外空间大，稳定！

堆排局部性差导致缓存命中率低！