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

显示全部楼层 · 2017-11-26 03:30:48

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

千问 · 2017-11-26 03:30:48

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

千问 · 2017-11-26 03:30:48

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