p*2
6 楼
quick sort O(1) memory吧?
s*e
8 楼
QuickSort递归栈的空间不算内存占用?
我觉得QS应该是时间复杂度O(nlogn),空间复杂度O(logn)的。
heapsort和quicksort适用面不一样。heap插入删除都是O(logn)的,而quicksort过的
数组如果要插入数据并且保持排序状态,插入要求是O(N)的,删除看具体数据结构而定。
quicksort的cpu cache friendly也要看情况,如果是链表做qs那很难做到每个node都
在cache中。就算是数组,qs里面左移的指针也不一定cache friendly。
我觉得QS应该是时间复杂度O(nlogn),空间复杂度O(logn)的。
heapsort和quicksort适用面不一样。heap插入删除都是O(logn)的,而quicksort过的
数组如果要插入数据并且保持排序状态,插入要求是O(N)的,删除看具体数据结构而定。
quicksort的cpu cache friendly也要看情况,如果是链表做qs那很难做到每个node都
在cache中。就算是数组,qs里面左移的指针也不一定cache friendly。
x*w
9 楼
In practice quick sort is faster,
I think this is because every iteration the array becomes more "tend to be
sorted" so less "swap" operation like heapsort. And if the number of
members is less than a certain limite, insert sort is taken place, which is
the best sorting method for "almost sorted" array.
【在 c********p 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 有啥不如quick sort的?
f*p
10 楼
在一般情况下,quick sort比heap sort快是因为下面几个原因。
1)quick sort没有事先的准备。heap sort一开始要建堆。
2) quick sort 在一个pass以后,分界的那个element就是最终结果,一个pass的cost
和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整,就
是差不多logn,乘积也差不多是nlogn。
3) 如果是多个cpu,多个thread,quick sort 绝对要比heap sort 强。
其实quick sort 主要的强的就是1)
1)quick sort没有事先的准备。heap sort一开始要建堆。
2) quick sort 在一个pass以后,分界的那个element就是最终结果,一个pass的cost
和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整,就
是差不多logn,乘积也差不多是nlogn。
3) 如果是多个cpu,多个thread,quick sort 绝对要比heap sort 强。
其实quick sort 主要的强的就是1)
c*p
11 楼
呜呜
cost
【在 f****p 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 在一般情况下,quick sort比heap sort快是因为下面几个原因。
: 1)quick sort没有事先的准备。heap sort一开始要建堆。
: 2) quick sort 在一个pass以后,分界的那个element就是最终结果,一个pass的cost
: 和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整,就
: 是差不多logn,乘积也差不多是nlogn。
: 3) 如果是多个cpu,多个thread,quick sort 绝对要比heap sort 强。
: 其实quick sort 主要的强的就是1)
cost
【在 f****p 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 在一般情况下,quick sort比heap sort快是因为下面几个原因。
: 1)quick sort没有事先的准备。heap sort一开始要建堆。
: 2) quick sort 在一个pass以后,分界的那个element就是最终结果,一个pass的cost
: 和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整,就
: 是差不多logn,乘积也差不多是nlogn。
: 3) 如果是多个cpu,多个thread,quick sort 绝对要比heap sort 强。
: 其实quick sort 主要的强的就是1)
f*p
12 楼
我其实还好少说了一个。
quick sort把一个分裂成两个的时候,理想情况是平均分。而下一步两个子表的长度都
是那个父表的一伴。而heap sort则不是。
你仔细观察这个动画。heap的准备和每一步做的都有。
http://en.wikipedia.org/wiki/Heapsort
如果一般情况下
quick sort cost = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ...
= n * log(n)
heap sort cost = sum [log(i)] for i = n, n-1, n-2, ..., 1
所以尽管heap sort 是 n log(n),quick sort基本上是最优的。
为了达到最优效果,对于大的n,一般还会做个randomization。很多randomized
algorithms就是这个思路。一般就一两遍就可以达到了,就是说再加上个n 或者 2n。
【在 c********p 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 呜呜
:
: cost
c*p
13 楼
这2天没力气想问题。。。
【在 f****p 的大作中提到】![](/moin_static193/solenoid/img/up.png)
:
: 我其实还好少说了一个。
: quick sort把一个分裂成两个的时候,理想情况是平均分。而下一步两个子表的长度都
: 是那个父表的一伴。而heap sort则不是。
: 你仔细观察这个动画。heap的准备和每一步做的都有。
: http://en.wikipedia.org/wiki/Heapsort
: 如果一般情况下
: quick sort cost = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ...
: = n * log(n)
: heap sort cost = sum [log(i)] for i = n, n-1, n-2, ..., 1
【在 f****p 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
:
: 我其实还好少说了一个。
: quick sort把一个分裂成两个的时候,理想情况是平均分。而下一步两个子表的长度都
: 是那个父表的一伴。而heap sort则不是。
: 你仔细观察这个动画。heap的准备和每一步做的都有。
: http://en.wikipedia.org/wiki/Heapsort
: 如果一般情况下
: quick sort cost = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ...
: = n * log(n)
: heap sort cost = sum [log(i)] for i = n, n-1, n-2, ..., 1
J*r
14 楼
good discussion
r*n
16 楼
irrespective of CPU caching, quick sort has another theoretical advantage
over heap sort: 3way-quick sort is entropy-optimal, O(nh) where h is the
entropy, whereas the other one is not.
if all the elements are truly uniformly distributed btw 0 and n-1, then h =
logn. however, for all other discrete distributions, h < logn and hence
quick sort is superior
over heap sort: 3way-quick sort is entropy-optimal, O(nh) where h is the
entropy, whereas the other one is not.
if all the elements are truly uniformly distributed btw 0 and n-1, then h =
logn. however, for all other discrete distributions, h < logn and hence
quick sort is superior
r*g
17 楼
quick sort是O(n^2)好吧。要O(nlogn),需要先randomize。quick sort还不是stable
的。以前说qsort快主要是cache line优化得好,如果是sort object的话其实都是一样
,我试过,用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
除对象的sorted heap对象。而现在大规模parallel,像MapReduce,其实MergeSort要
好得多。
【在 f****p 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 笨死!在那些O(nlogn)的算法中,有两个常数就是说cost = A*(nlogn) + B。
: on average,quick sort的这两个常数都是最小的。
的。以前说qsort快主要是cache line优化得好,如果是sort object的话其实都是一样
,我试过,用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
除对象的sorted heap对象。而现在大规模parallel,像MapReduce,其实MergeSort要
好得多。
【在 f****p 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 笨死!在那些O(nlogn)的算法中,有两个常数就是说cost = A*(nlogn) + B。
: on average,quick sort的这两个常数都是最小的。
f*p
18 楼
我一直在说是平均情况,你自己去看。那个O(n^2)是在倒序的情况。你自己随便用个数
据你就比较一下就知道了,在实际情况下,都差不多是随机的,quick sort快的不是一
点半点。这个和architecture什么基本没毛关系。很多时候,重要的是不是in-place的
排序。特别是大的数据库或者storage的时候,所以有时那个只用merge sort。
stable
【在 r**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: quick sort是O(n^2)好吧。要O(nlogn),需要先randomize。quick sort还不是stable
: 的。以前说qsort快主要是cache line优化得好,如果是sort object的话其实都是一样
: ,我试过,用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
: 除对象的sorted heap对象。而现在大规模parallel,像MapReduce,其实MergeSort要
: 好得多。
据你就比较一下就知道了,在实际情况下,都差不多是随机的,quick sort快的不是一
点半点。这个和architecture什么基本没毛关系。很多时候,重要的是不是in-place的
排序。特别是大的数据库或者storage的时候,所以有时那个只用merge sort。
stable
【在 r**********g 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: quick sort是O(n^2)好吧。要O(nlogn),需要先randomize。quick sort还不是stable
: 的。以前说qsort快主要是cache line优化得好,如果是sort object的话其实都是一样
: ,我试过,用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
: 除对象的sorted heap对象。而现在大规模parallel,像MapReduce,其实MergeSort要
: 好得多。
k*t
19 楼
学习啦
cost
【在 f****p 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 在一般情况下,quick sort比heap sort快是因为下面几个原因。
: 1)quick sort没有事先的准备。heap sort一开始要建堆。
: 2) quick sort 在一个pass以后,分界的那个element就是最终结果,一个pass的cost
: 和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整,就
: 是差不多logn,乘积也差不多是nlogn。
: 3) 如果是多个cpu,多个thread,quick sort 绝对要比heap sort 强。
: 其实quick sort 主要的强的就是1)
cost
【在 f****p 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 在一般情况下,quick sort比heap sort快是因为下面几个原因。
: 1)quick sort没有事先的准备。heap sort一开始要建堆。
: 2) quick sort 在一个pass以后,分界的那个element就是最终结果,一个pass的cost
: 和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整,就
: 是差不多logn,乘积也差不多是nlogn。
: 3) 如果是多个cpu,多个thread,quick sort 绝对要比heap sort 强。
: 其实quick sort 主要的强的就是1)
s*5
20 楼
那用randomize数组啊?每次randomly选一个pivot index就可以保证不会到O(n^2)了。
只要不是在distributed cluster上,quick sort应该最快的。在cluster上用merge
sort最方便了。
stable
【在 r**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: quick sort是O(n^2)好吧。要O(nlogn),需要先randomize。quick sort还不是stable
: 的。以前说qsort快主要是cache line优化得好,如果是sort object的话其实都是一样
: ,我试过,用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
: 除对象的sorted heap对象。而现在大规模parallel,像MapReduce,其实MergeSort要
: 好得多。
只要不是在distributed cluster上,quick sort应该最快的。在cluster上用merge
sort最方便了。
stable
【在 r**********g 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: quick sort是O(n^2)好吧。要O(nlogn),需要先randomize。quick sort还不是stable
: 的。以前说qsort快主要是cache line优化得好,如果是sort object的话其实都是一样
: ,我试过,用java写qsort还不如heap sort快。heap sort很适合用在需要不断添加删
: 除对象的sorted heap对象。而现在大规模parallel,像MapReduce,其实MergeSort要
: 好得多。
d*l
21 楼
In my opinion, quicksort() is better because the CPU cache thing, has better
locality of reference -- the next thing to be accessed is usually close in
memory to the thing you just looked at. In java, java.util.Arrays.sort()
uses quicksort(), while java.util.Collections.sort() use mergesort().
As for heapsort(), it doesn't build a real heap(tree-heap), it is array/
arraylist in fact, through the index jumping, give us an illusion of a heap.
By the way, bless for myself recent onsite. ^_^
【在 s***5 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 那用randomize数组啊?每次randomly选一个pivot index就可以保证不会到O(n^2)了。
: 只要不是在distributed cluster上,quick sort应该最快的。在cluster上用merge
: sort最方便了。
:
: stable
locality of reference -- the next thing to be accessed is usually close in
memory to the thing you just looked at. In java, java.util.Arrays.sort()
uses quicksort(), while java.util.Collections.sort() use mergesort().
As for heapsort(), it doesn't build a real heap(tree-heap), it is array/
arraylist in fact, through the index jumping, give us an illusion of a heap.
By the way, bless for myself recent onsite. ^_^
【在 s***5 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 那用randomize数组啊?每次randomly选一个pivot index就可以保证不会到O(n^2)了。
: 只要不是在distributed cluster上,quick sort应该最快的。在cluster上用merge
: sort最方便了。
:
: stable
f*b
22 楼
mark
h*o
23 楼
我曾经问过本版: QuickSort递归栈的空间算不算内存占用?没得到回答。
我现在觉得空间复杂度O(1)。因为可以tail recursive.
定。
【在 s***e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: QuickSort递归栈的空间不算内存占用?
: 我觉得QS应该是时间复杂度O(nlogn),空间复杂度O(logn)的。
: heapsort和quicksort适用面不一样。heap插入删除都是O(logn)的,而quicksort过的
: 数组如果要插入数据并且保持排序状态,插入要求是O(N)的,删除看具体数据结构而定。
: quicksort的cpu cache friendly也要看情况,如果是链表做qs那很难做到每个node都
: 在cache中。就算是数组,qs里面左移的指针也不一定cache friendly。
我现在觉得空间复杂度O(1)。因为可以tail recursive.
定。
【在 s***e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: QuickSort递归栈的空间不算内存占用?
: 我觉得QS应该是时间复杂度O(nlogn),空间复杂度O(logn)的。
: heapsort和quicksort适用面不一样。heap插入删除都是O(logn)的,而quicksort过的
: 数组如果要插入数据并且保持排序状态,插入要求是O(N)的,删除看具体数据结构而定。
: quicksort的cpu cache friendly也要看情况,如果是链表做qs那很难做到每个node都
: 在cache中。就算是数组,qs里面左移的指针也不一定cache friendly。
h*o
24 楼
相关阅读
samsung公司如何?读博期间可以full-time工作吗?求推荐 设计模式书求推荐一本有助于 J2EE interview 的书简历有误,background check会不会有问题新人,问关于我的Work authorization问题怎么回答 ?member of technical staff 跟SW engineer 有区别么?面试题目的次序对发挥会有影响?问道老题2页简历要加页码吗大家最害怕什么类型的题?在公司看来研究生读书期间经历算不算 招聘启示上要求的 2+ years of development experience.OPT 60+90天? (转载)上周四有个local的面试,结束时manager说这周一会做决定请教问题,在线等!real-time system这块方向好找工作不职位明说要c++ for linux的,如果没用过是不是基本没戏?想问下opt开始时间11月中旬和12月初面试区别大不大?大家LCA一般几天批下来的?