c********p
发帖数: 1969 | |
l*******0
发帖数: 63 | |
f****p
发帖数: 18483 | 3 笨死！在那些O(nlogn)的算法中，有两个常数就是说cost = A*(nlogn) + B。
on average，quick sort的这两个常数都是最小的。
【在 c********p 的大作中提到】
: 有啥不如quick sort的？
|
c********p
发帖数: 1969 | 4 quick sort最不济的时候，要n吧？！
【在 f****p 的大作中提到】
: 笨死！在那些O(nlogn)的算法中，有两个常数就是说cost = A*(nlogn) + B。
: on average，quick sort的这两个常数都是最小的。
|
e*****t
发帖数: 1005 | 5 n^2
【在 c********p 的大作中提到】
: quick sort最不济的时候，要n吧？！
|
p*****2
发帖数: 21240 | 6 quick sort O(1) memory吧？ |
l*******m
发帖数: 1096 | 7 quick sort 快，因为cpu cache friendly。搞搞数值算法就知道现在CPU的运算单元一
般都不会跑满，CPU io花好多时间，由于heap操作，index是跳来跳去的，cache
reloading太多。而quick sort， index 是滑动的，所以overhead低
【在 c********p 的大作中提到】
: 有啥不如quick sort的？
|
s***e
发帖数: 403 | 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。 |
x*********w
发帖数: 533 | 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 的大作中提到】
: 有啥不如quick sort的？
|
f****p
发帖数: 18483 | 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) |
|
|
c********p
发帖数: 1969 | 11 呜呜
cost
【在 f****p 的大作中提到】
: 在一般情况下，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
发帖数: 18483 | 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 的大作中提到】
: 呜呜
:
: cost
|
c********p
发帖数: 1969 | 13 这2天没力气想问题。。。
【在 f****p 的大作中提到】
:
: 我其实还好少说了一个。
: 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
发帖数: 5921 | |
b****g
发帖数: 63 | 15 O(log(n)) to hold the recursion call stack.
【在 p*****2 的大作中提到】
: quick sort O(1) memory吧？
|
r*********n
发帖数: 4553 | 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 |
r**********g
发帖数: 22734 | 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 的大作中提到】
: 笨死！在那些O(nlogn)的算法中，有两个常数就是说cost = A*(nlogn) + B。
: on average，quick sort的这两个常数都是最小的。
|
f****p
发帖数: 18483 | 18 我一直在说是平均情况，你自己去看。那个O(n^2)是在倒序的情况。你自己随便用个数
据你就比较一下就知道了，在实际情况下，都差不多是随机的，quick sort快的不是一
点半点。这个和architecture什么基本没毛关系。很多时候，重要的是不是in-place的
排序。特别是大的数据库或者storage的时候，所以有时那个只用merge sort。
stable
【在 r**********g 的大作中提到】
: 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
发帖数: 144 | 19 学习啦
cost
【在 f****p 的大作中提到】
: 在一般情况下，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
发帖数: 2136 | 20 那用randomize数组啊？每次randomly选一个pivot index就可以保证不会到O(n^2)了。
只要不是在distributed cluster上，quick sort应该最快的。在cluster上用merge
sort最方便了。
stable
【在 r**********g 的大作中提到】
: 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
发帖数: 98 | 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 的大作中提到】
: 那用randomize数组啊？每次randomly选一个pivot index就可以保证不会到O(n^2)了。
: 只要不是在distributed cluster上，quick sort应该最快的。在cluster上用merge
: sort最方便了。
:
: stable
|
f*******b
发帖数: 520 | |
h**o
发帖数: 548 | 23 我曾经问过本版: QuickSort递归栈的空间算不算内存占用？没得到回答。
我现在觉得空间复杂度O(1)。因为可以tail recursive.
定。
【在 s***e 的大作中提到】
: 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
发帖数: 548 | 24 Hi,
qsort： nlogn = log n^n
heapsort：sum(log(i)) = log (n!) < log n^n
为什么 qsort 常数因子最小最优那？
【在 f****p 的大作中提到】
: 我一直在说是平均情况，你自己去看。那个O(n^2)是在倒序的情况。你自己随便用个数
: 据你就比较一下就知道了，在实际情况下，都差不多是随机的，quick sort快的不是一
: 点半点。这个和architecture什么基本没毛关系。很多时候，重要的是不是in-place的
: 排序。特别是大的数据库或者storage的时候，所以有时那个只用merge sort。
:
: stable
|
