g***j
发帖数: 1275 | 1 为啥quicksort的空间是lgN, 为啥mergesort的最坏的情况是N? 一般情况是什么？
quicksort, mergesort, heapsort，如何选择用哪个sort？ 我只知道mergesort
stable，那么quicksort和heapsort的差别呢？除了worse case quicksort是n^2
另外，是不是只要涉及到交换的，都不stable? |
g***j
发帖数: 1275 | 2 自己顶一下
【在 g***j 的大作中提到】
: 为啥quicksort的空间是lgN, 为啥mergesort的最坏的情况是N? 一般情况是什么？
: quicksort, mergesort, heapsort，如何选择用哪个sort？ 我只知道mergesort
: stable，那么quicksort和heapsort的差别呢？除了worse case quicksort是n^2
: 另外，是不是只要涉及到交换的，都不stable?
|
x*******6
发帖数: 262 | 3 quicksort空间是O(1)吧，mergesort有最坏情况？一直都是O（nlogn）时间O（n）空间
吧。
磁盘上mergesort有优势。heapsort效率和quicksort相当但是多些额外操作所以一般没
人用吧。 |
l***i
发帖数: 1309 | 4 quicksort needs to maintain a stack of logn, either explicitly or by the
compiler implicitly. |
o***d
发帖数: 313 | 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********d
发帖数: 7742 | 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**********x
发帖数: 4083 | 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****r
发帖数: 807 | 8 lz, 关于sort的特点，ls说的都很好了。
对于你的困惑about lgn space of quicksort，我个人认为是quicksort没层递归需要
为stack存下partition point，这样一层一层的，需要lgn space。
我自己的理解，不知道对不对。 |
r********d
发帖数: 7742 | 9 btw, 递归不仅仅是存partition point，递归的过程中堆栈会存储所有function call
和相关变量的信息。
【在 k****r 的大作中提到】
: lz, 关于sort的特点，ls说的都很好了。
: 对于你的困惑about lgn space of quicksort，我个人认为是quicksort没层递归需要
: 为stack存下partition point，这样一层一层的，需要lgn space。
: 我自己的理解，不知道对不对。
|
k****r
发帖数: 807 | 10 只是递归这样，还是所有call function这样？
call
【在 r********d 的大作中提到】
: btw, 递归不仅仅是存partition point，递归的过程中堆栈会存储所有function call
: 和相关变量的信息。
|
|
|
d**********x
发帖数: 4083 | 11 任何function call都这样
不过64bit的堆栈已经大幅简化了
【在 k****r 的大作中提到】
: 只是递归这样，还是所有call function这样？
:
: call
|
g***j
发帖数: 1275 | 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***j
发帖数: 1275 | 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**h
发帖数: 509 | 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********d
发帖数: 7742 | 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********d
发帖数: 7742 | 16 多谢补充，学习了。
【在 d**********x 的大作中提到】
: 作为一个补充，stl的sort是introsort，除了这里提到的对quicksort的优化以外，还
: 可能会在quicksort递归深度过深的时候切换成heapsort
:
: median-
: factor
|
r********d
发帖数: 7742 | 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
|
