为什么快速排序比堆排序快呢？

Question

快速排序的：最坏情况o(n^2),最好情况o(nlog2n)，占用空间o(nlog2n)
堆排序：最坏和最好情况都是o(nlog2n)，占用空间o(1)
时间复杂度和空间复杂度堆排序都完爆快排，为什么实际使用都用快速排序？难不成快速排序比堆排序快？

Answer 1

一般情况下，快速排序效率要高于堆排序。因为堆排序的常数较大（不过也是1～2之间吧）。
快速排序的平均时间复杂度是O(1.39nlogn)。一般来说，除非有需要绝对保证不能出现O(n^2)的要求，不使用堆排。
堆排序需要有效的随机存取。

Answer 2

因为推排中有大量无效的操作，比如将最末尾元素移动到堆首，必须要有后续操作再移动此时堆首的元素，这样会增加数据的无序度；但是快排不一样，快排没有无用操作，每一次交换都会使数据更加有序。而且堆排是跳跃访问，快排是局部顺序访问，这两者的速度实际上是不一样的，当数据量增大差距就明显了

Answer 3

你去看看c语言自带的sort 排序函数吧，藐视也是快排，建议你去看看什么是分摊准则，在小数据的情况下，选择快排比较好，不是 什么完爆不完爆的问题 大哥

Answer 4

数据结构我不大记得了，不过实际使用是用快速排序的话可能是开发人员的喜欢，历史版本的统一，或者是以硬件换速度吧。