z****e
发帖数: 2024 | 1 比较 heapsort , quicksort
我怎么觉得从理论上说heapsort比quicksort 好呢？
那为什么大部分书都说 "in practice, quicksort beats heapsort"
看到有个文献是从entropy的角度考虑这个问题。太长了，结论也不清楚。
哪位大侠肯出手相救？ |
T*****9
发帖数: 2484 | 2 worst case: heap sort better
average case: quick sort better
【在 z****e 的大作中提到】
: 比较 heapsort , quicksort
: 我怎么觉得从理论上说heapsort比quicksort 好呢？
: 那为什么大部分书都说 "in practice, quicksort beats heapsort"
: 看到有个文献是从entropy的角度考虑这个问题。太长了，结论也不清楚。
: 哪位大侠肯出手相救？
|
z****e
发帖数: 2024 | 3 “ average case: quick sort better”
are you sure? why?
【在 T*****9 的大作中提到】
: worst case: heap sort better
: average case: quick sort better
|
z****e
发帖数: 2024 | 4 计算机系主任对此问题回复：大家好文共赏
A very good question. Which of the two is faster in practice depends
on a lot of factors, including how you implement each of them. Quicksort
has less random access of memory. You are absolutely right
that quick sort could be much worse than heapsort in some
cases.
I used quick sort to illustrate the technique (e.g., one could
adapt to select the kth smallest item) and not so much because
it was the fastest algorithm. |
e*****w
发帖数: 144 | 5 是的。平均复杂度都是nlogn但是quick sort的常数因子比较小。
【在 z****e 的大作中提到】
: “ average case: quick sort better”
: are you sure? why?
|
