问一个排序的问题 - 未名空间MITBBS历史存档

g*j2012-12-12 08:12

1 楼

为啥quicksort的空间是lgN, 为啥mergesort的最坏的情况是N? 一般情况是什么？
quicksort, mergesort, heapsort，如何选择用哪个sort？我只知道mergesort
stable，那么quicksort和heapsort的差别呢？除了worse case quicksort是n^2
另外，是不是只要涉及到交换的，都不stable?

g*j2012-12-12 08:12

2 楼

自己顶一下

【在 g***j 的大作中提到】

: 为啥quicksort的空间是lgN, 为啥mergesort的最坏的情况是N? 一般情况是什么？
: quicksort, mergesort, heapsort，如何选择用哪个sort？我只知道mergesort
: stable，那么quicksort和heapsort的差别呢？除了worse case quicksort是n^2
: 另外，是不是只要涉及到交换的，都不stable?

x*62012-12-12 08:12

3 楼

quicksort空间是O(1)吧，mergesort有最坏情况？一直都是O（nlogn）时间O（n）空间
吧。
磁盘上mergesort有优势。heapsort效率和quicksort相当但是多些额外操作所以一般没
人用吧。

l*i2012-12-12 08:12

4 楼

quicksort needs to maintain a stack of logn, either explicitly or by the
compiler implicitly.

o*d2012-12-12 08:12

5 楼

space complexity of quicksort should be ologn, right? not o1 because of the
stack depth

【在 x*******6 的大作中提到】

: quicksort空间是O(1)吧，mergesort有最坏情况？一直都是O（nlogn）时间O（n）空间
: 吧。
: 磁盘上mergesort有优势。heapsort效率和quicksort相当但是多些额外操作所以一般没
: 人用吧。

r*d2012-12-12 08:12

6 楼

每种sort都有自己的优势和劣势，它们各自都有存在的道理。
quicksort有最好的实践效率。同时是in-place。配上random pivot/shuffle，median-
of-K 和少量元素转insertion sort是最实用的排序方法。O(n^2)复杂度是极其小概率
事件，一般不会发生。同时因为其对硬件cache的应用效率较高，实践中Quicksort很难
被beat, 因为cache的访问速度比内存寻址快两个数量级。
Mergesort的优势是stable以及在external sort中的使用. 理论分析时候的也会用到
worstcase n(log(n))。同时基本的merge想法和变形，不需要random access, 常常用
在很多其他问题的解决之中。比如说merge lists。但是megersort的constant factor
比较大，是quicksort的好几倍。一般比Quicksort慢。
Heapsort因为在时间上和空间上都是最优，在很多论文只要涉及到sort都会用它做理论
分析。constant factor还不错，比merge sort的好。但是它的致命弱点是对cache利用
的不好，比如说max-heapify的过程中，很少有相邻元素的处理。虽然有这些缺点，有
时小规模排序时还是有用。
并不是涉及到交换的都是不stable，比如说insertion sort就是stable的。关键要看交
换的过程是怎么样的。
如果要想真正理解这些算法，建议把基本的排序算法及其改进和变形都实现一下，同时
分析它的基本操作，时间空间复杂度。然后在不同大小和类型的数据集上运行一下这些
算法，分析结果，你就会有更深入的了解。

【在 g***j 的大作中提到】

: 为啥quicksort的空间是lgN, 为啥mergesort的最坏的情况是N? 一般情况是什么？
: quicksort, mergesort, heapsort，如何选择用哪个sort？我只知道mergesort
: stable，那么quicksort和heapsort的差别呢？除了worse case quicksort是n^2
: 另外，是不是只要涉及到交换的，都不stable?

d*x2012-12-12 08:12

7 楼

作为一个补充，stl的sort是introsort，除了这里提到的对quicksort的优化以外，还
可能会在quicksort递归深度过深的时候切换成heapsort

median-
factor

【在 r********d 的大作中提到】

: 每种sort都有自己的优势和劣势，它们各自都有存在的道理。
: quicksort有最好的实践效率。同时是in-place。配上random pivot/shuffle，median-
: of-K 和少量元素转insertion sort是最实用的排序方法。O(n^2)复杂度是极其小概率
: 事件，一般不会发生。同时因为其对硬件cache的应用效率较高，实践中Quicksort很难
: 被beat, 因为cache的访问速度比内存寻址快两个数量级。
: Mergesort的优势是stable以及在external sort中的使用. 理论分析时候的也会用到
: worstcase n(log(n))。同时基本的merge想法和变形，不需要random access, 常常用
: 在很多其他问题的解决之中。比如说merge lists。但是megersort的constant factor
: 比较大，是quicksort的好几倍。一般比Quicksort慢。
: Heapsort因为在时间上和空间上都是最优，在很多论文只要涉及到sort都会用它做理论

k*r2012-12-12 08:12

8 楼

lz, 关于sort的特点，ls说的都很好了。
对于你的困惑about lgn space of quicksort，我个人认为是quicksort没层递归需要
为stack存下partition point，这样一层一层的，需要lgn space。
我自己的理解，不知道对不对。

r*d2012-12-12 08:12

9 楼

btw, 递归不仅仅是存partition point，递归的过程中堆栈会存储所有function call
和相关变量的信息。

【在 k****r 的大作中提到】

: lz, 关于sort的特点，ls说的都很好了。
: 对于你的困惑about lgn space of quicksort，我个人认为是quicksort没层递归需要
: 为stack存下partition point，这样一层一层的，需要lgn space。
: 我自己的理解，不知道对不对。

k*r2012-12-12 08:12

10 楼

只是递归这样，还是所有call function这样？

call

【在 r********d 的大作中提到】

: btw, 递归不仅仅是存partition point，递归的过程中堆栈会存储所有function call
: 和相关变量的信息。

d*x2012-12-12 08:12

11 楼

任何function call都这样
不过64bit的堆栈已经大幅简化了

【在 k****r 的大作中提到】

: 只是递归这样，还是所有call function这样？
:
: call

g*j2012-12-12 08:12

12 楼

谢谢大牛指点！能不能详细谈谈这里的cache的问题，我一直困惑的是为啥heapsort用
得少，既然你谈到了他的致命的弱点，我还是不太清楚，请可以详细谈谈么？
另外，你这里constant factor具体指的什么？是 cNlgN里面的c么？

median-
factor

【在 r********d 的大作中提到】

: 每种sort都有自己的优势和劣势，它们各自都有存在的道理。
: quicksort有最好的实践效率。同时是in-place。配上random pivot/shuffle，median-
: of-K 和少量元素转insertion sort是最实用的排序方法。O(n^2)复杂度是极其小概率
: 事件，一般不会发生。同时因为其对硬件cache的应用效率较高，实践中Quicksort很难
: 被beat, 因为cache的访问速度比内存寻址快两个数量级。
: Mergesort的优势是stable以及在external sort中的使用. 理论分析时候的也会用到
: worstcase n(log(n))。同时基本的merge想法和变形，不需要random access, 常常用
: 在很多其他问题的解决之中。比如说merge lists。但是megersort的constant factor
: 比较大，是quicksort的好几倍。一般比Quicksort慢。
: Heapsort因为在时间上和空间上都是最优，在很多论文只要涉及到sort都会用它做理论

g*j2012-12-12 08:12

13 楼

另外你说的insertion sorting, 应该不是用到了交换吧，它应该用到的是平移和插入
，跟quicksort和heapsort里面的纯交换两个元素的位置，不是一个意思吧？

median-
factor

【在 r********d 的大作中提到】

: 每种sort都有自己的优势和劣势，它们各自都有存在的道理。
: quicksort有最好的实践效率。同时是in-place。配上random pivot/shuffle，median-
: of-K 和少量元素转insertion sort是最实用的排序方法。O(n^2)复杂度是极其小概率
: 事件，一般不会发生。同时因为其对硬件cache的应用效率较高，实践中Quicksort很难
: 被beat, 因为cache的访问速度比内存寻址快两个数量级。
: Mergesort的优势是stable以及在external sort中的使用. 理论分析时候的也会用到
: worstcase n(log(n))。同时基本的merge想法和变形，不需要random access, 常常用
: 在很多其他问题的解决之中。比如说merge lists。但是megersort的constant factor
: 比较大，是quicksort的好几倍。一般比Quicksort慢。
: Heapsort因为在时间上和空间上都是最优，在很多论文只要涉及到sort都会用它做理论

u*h2012-12-12 08:12

14 楼

正解。

median-
factor

【在 r********d 的大作中提到】

: 每种sort都有自己的优势和劣势，它们各自都有存在的道理。
: quicksort有最好的实践效率。同时是in-place。配上random pivot/shuffle，median-
: of-K 和少量元素转insertion sort是最实用的排序方法。O(n^2)复杂度是极其小概率
: 事件，一般不会发生。同时因为其对硬件cache的应用效率较高，实践中Quicksort很难
: 被beat, 因为cache的访问速度比内存寻址快两个数量级。
: Mergesort的优势是stable以及在external sort中的使用. 理论分析时候的也会用到
: worstcase n(log(n))。同时基本的merge想法和变形，不需要random access, 常常用
: 在很多其他问题的解决之中。比如说merge lists。但是megersort的constant factor
: 比较大，是quicksort的好几倍。一般比Quicksort慢。
: Heapsort因为在时间上和空间上都是最优，在很多论文只要涉及到sort都会用它做理论

r*d2012-12-12 08:12

15 楼

Insertion sort 可以交换实现，比如说我这样写：
void insertionsort(vector &v) {
for (int i = 1; i < v.size(); ++i)
for (int j = i-1; j>=0 && v[j] > v[j+1]; --j)
swap(v, j, j+1);
}
交换到底是否影响stability，主要看交换是怎么做的，stable就是说值相同的情况下
保持原序。所以只要
你的交换是按着顺序来就没问题。所以关键是看怎么换，和谁换。

【在 g***j 的大作中提到】

: 另外你说的insertion sorting, 应该不是用到了交换吧，它应该用到的是平移和插入
: ，跟quicksort和heapsort里面的纯交换两个元素的位置，不是一个意思吧？
:
: median-
: factor

r*d2012-12-12 08:12

16 楼

多谢补充，学习了。

【在 d**********x 的大作中提到】

: 作为一个补充，stl的sort是introsort，除了这里提到的对quicksort的优化以外，还
: 可能会在quicksort递归深度过深的时候切换成heapsort
:
: median-
: factor

r*d2012-12-12 08:12

17 楼

Cache就是数据locality的问题。Cache都小，但是快。所以如果程序处理的数据都是连
续的，或者说有很好locality的特性，Cache hit概率就大，运行就快。
关于Constant factor，就是那个C。有很多影响因素，先说俩个。
1) 你如果仔细分析算法的话，是可以数出基本步数的，比如有的算法是6n步，有的是
2n步，循环6次和循环两次都是O(n)，但是执行时间肯定是不一样的。
2) 每一步的内容，拿排序来说，基本操作有交换和比较，虽然都是基本操作，但是花
费是不一样的。这也会影响程序快慢。
不用客气，我解释的过程也是整理思路的过程，自己也受益匪浅。

【在 g***j 的大作中提到】

: 谢谢大牛指点！能不能详细谈谈这里的cache的问题，我一直困惑的是为啥heapsort用
: 得少，既然你谈到了他的致命的弱点，我还是不太清楚，请可以详细谈谈么？
: 另外，你这里constant factor具体指的什么？是 cNlgN里面的c么？
:
: median-
: factor