m***p
发帖数: 86 | 1 quicksort时间最差是O(n^2)
mergesort空间上需要O(n)
heapsort时间最差是O(nlogn),空间只需要O(1),为什么提到的频率没有上面两个高呢?
是比较复杂还是其他什么原因? |
w**2
发帖数: 8 | 2 1.quicksort 随机化后 nlogn 时间
2.mergesort 链表上 O(1)空间
3.heapsort 需要O(n)辅助空间 除非只是打印 |
r******l
发帖数: 10760 | 3 复杂度跟实际速度是两码事。quick sort平均来说是最快的。
?
【在 m***p 的大作中提到】
: quicksort时间最差是O(n^2)
: mergesort空间上需要O(n)
: heapsort时间最差是O(nlogn),空间只需要O(1),为什么提到的频率没有上面两个高呢?
: 是比较复杂还是其他什么原因?
|
l*******b
发帖数: 2586 | 4 heapsort 可以 in place 呀
【在 w**2 的大作中提到】
: 1.quicksort 随机化后 nlogn 时间
: 2.mergesort 链表上 O(1)空间
: 3.heapsort 需要O(n)辅助空间 除非只是打印
|
e********3
发帖数: 18578 | 5 quicksort也可以in place.
【在 l*******b 的大作中提到】
: heapsort 可以 in place 呀
|
y*******g
发帖数: 6599 | 6 quicksort操作的是local memory
?
【在 m***p 的大作中提到】
: quicksort时间最差是O(n^2)
: mergesort空间上需要O(n)
: heapsort时间最差是O(nlogn),空间只需要O(1),为什么提到的频率没有上面两个高呢?
: 是比较复杂还是其他什么原因?
|
p*****2
发帖数: 21240 | 7 大牛 听说你最近很美？
【在 y*******g 的大作中提到】
: quicksort操作的是local memory
:
: ?
|
j****y
发帖数: 684 | 8 heapsort 很多修改index，在内存里跳来跳去
一堆cache miss，能快就鬼了。
?
【在 m***p 的大作中提到】
: quicksort时间最差是O(n^2)
: mergesort空间上需要O(n)
: heapsort时间最差是O(nlogn),空间只需要O(1),为什么提到的频率没有上面两个高呢?
: 是比较复杂还是其他什么原因?
|
V*********r
发帖数: 666 | 9 堆排序很常用啊。之所以在“面试”中不常出，准确的说法是不常考其实现，无非两个
原因：
1. 白板篇幅有限，heapify/siftup/siftdown全写完白板容不下。
2. quicksort/mergesort变种很多，可inplace可外借空间，可迭代可递归（比如考你
非inplace的迭代式mergesort），是分治思想的典型代表，容易形成考点。而且其思想
适用于任何线性表（不管是数组还是链式存储），也可扩展到树形存储。考点密集不奇
怪。
?
【在 m***p 的大作中提到】
: quicksort时间最差是O(n^2)
: mergesort空间上需要O(n)
: heapsort时间最差是O(nlogn),空间只需要O(1),为什么提到的频率没有上面两个高呢?
: 是比较复杂还是其他什么原因?
|
J*****a
发帖数: 4262 | 10 quick sort在实践中是最快的，你可以看看相关文献
而且quicksort有很多变种，改变pivot的选取，或者三头并进，能大大提高最坏情况的
性能 |
L***s
发帖数: 1148 | 11 “实践中”要考虑的情况可就多了，比如locality of reference、输入数据已经部分
有序、排序稳定性、内存不够要外排序、多机并行排序 等等，工程中的默认实用排序
一般都是mergesort的变种，也就是两轮或两轮以上的混合排序：最后一轮mergesort，
前面几轮找sorted runs to be merged的方法八仙过海各显神通（比如简单地插入排序
、双pivot快排等等）。
楼主明显是说面试的情况，不必考虑这么多工程上的因素。
【在 J*****a 的大作中提到】
: quick sort在实践中是最快的，你可以看看相关文献
: 而且quicksort有很多变种，改变pivot的选取，或者三头并进，能大大提高最坏情况的
: 性能
|
t***t
发帖数: 6066 | 12 quicksort是O(nlogn)算法中常数最小的。 |
G*********n
发帖数: 53 | 13 因为 Heapsort 会有大量的 cache 的in & out， 对cache利用不充分，所以用的最少
。对于 mergesort 需要分配一个 新的array来help，所以速度也没有比quick sort快
。相对来说，quicksort最快 |
