q****x
发帖数: 7404 | 1 is it possible?
if yes, how?
if not, why? | g***s
发帖数: 3811 | 2 yes. since getting the median is O(n) and you can you the median to do
partition.
【在 q****x 的大作中提到】
: is it possible?
: if yes, how?
: if not, why?
| q****x
发帖数: 7404 | 3 you mean use that worst case O(n) get_median() algorithm? cool.
【在 g***s 的大作中提到】
: yes. since getting the median is O(n) and you can you the median to do
: partition.
| l***i
发帖数: 1309 | 4 Although in practice O(n)-median algorithm carries a large constant so will
likely defeat the small constant advantage of quick-sort compared to other O
(nlogn) sorting algorithms. |
|
