z****e
发帖数: 2024 | 1 请问 heapsort vs. quicksort.
基本的不提了，什么 worst case, pre-sorted, in place, etc.
不明白，看到一些资料，说 in practice, quicksort beats heapsort, because
quicksort has less comparisons on average.
有这么一说吗？觉得 less comparisons 这句话挺深刻的，有什么文献提到两者的比
较？
谢谢。 | h*******e
发帖数: 225 | 2 I dont think quicksort has less comparisons on average. It really depends on
how you implement them. For example, using William's original heapify
algorithm, you need 2nlogn + O(n) comparisons, whereas using Floyd's heapify
algorithm, you only need nlogn + O(n) on average. There are many variants
for quicksort too.
The reason why quicksort generally beats heapsort is largely due to the data
access pattern. It has better cache locality.
【在 z****e 的大作中提到】
: 请问 heapsort vs. quicksort.
: 基本的不提了，什么 worst case, pre-sorted, in place, etc.
: 不明白，看到一些资料，说 in practice, quicksort beats heapsort, because
: quicksort has less comparisons on average.
: 有这么一说吗？觉得 less comparisons 这句话挺深刻的，有什么文献提到两者的比
: 较？
: 谢谢。
| T**********n
发帖数: 480 | 3 quicksort beat heapsort是因为Cache Locality减少了缓存抖动
要说更深刻的原因可以说机器的结构针对quicksort做了优化
【在 z****e 的大作中提到】
: 请问 heapsort vs. quicksort.
: 基本的不提了，什么 worst case, pre-sorted, in place, etc.
: 不明白，看到一些资料，说 in practice, quicksort beats heapsort, because
: quicksort has less comparisons on average.
: 有这么一说吗？觉得 less comparisons 这句话挺深刻的，有什么文献提到两者的比
: 较？
: 谢谢。
|
|
