w******g
发帖数: 67 | 1 刚开始看书，理解不够深刻，哪位大侠给科普一下。
1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢？
2. 看到以前有例子说n非常大的话用merge sort，几台机器分别sort，然后再merge，
这是为什么
呢？merge sort 不是需要而外的空间～n 吗？这时候用quicksort 会不会好一些？
多谢。 |
s*********t
发帖数: 1663 | 2 heap sort很常用，比如找top k，动态的，就可以开个k size的heap
merge sort我在搜索引擎的应用里用过，搜两个关键字，索引返回两个集合，这时候需
要合并。 这两个集合应该是有序的，此时只需要merge sort的merge即可。
qsort很省事，一般的排序，算法题目，都可以使用。
【在 w******g 的大作中提到】
: 刚开始看书，理解不够深刻，哪位大侠给科普一下。
: 1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢？
: 2. 看到以前有例子说n非常大的话用merge sort，几台机器分别sort，然后再merge，
: 这是为什么
: 呢？merge sort 不是需要而外的空间～n 吗？这时候用quicksort 会不会好一些？
: 多谢。
|
l*******y
发帖数: 1498 | 3 quick sort时间依赖于pviot，最好情况下才是nlgn，但是有较好的cache behavior.
heap sort 最差情况下是nlgn，但是heap sort 有很多random access，如果数据是从
high latency的设备上读的话会比较慢。
merge sort最差是nlgn，需要额外的空间(上面2个sort都可以in place完成)，也有比较好的cache behavior，还有merge sort更容易parallelize |
r*d
发帖数: 896 | 4 merge sort是stable的
quick sort是unstable
如果要保留原数据的顺序，要用merge sort
也有stable quick sort，不过比较复杂
【在 w******g 的大作中提到】
: 刚开始看书，理解不够深刻，哪位大侠给科普一下。
: 1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢？
: 2. 看到以前有例子说n非常大的话用merge sort，几台机器分别sort，然后再merge，
: 这是为什么
: 呢？merge sort 不是需要而外的空间～n 吗？这时候用quicksort 会不会好一些？
: 多谢。
|
y*********e
发帖数: 518 | 5 O(nlogn):
qsort 和 mergesort 都可以达到O(nlogn)，但是 qsort 的常数因子比 mergesort 低
很多。所以，一般情况下 qsort 会更快。
O(n^2):
虽然 qsort 的最坏情况是 O(n^2)，但是要达到这个最坏情况不容易。对于实现的较好
randomized qsort，达到这个最坏情况的几率接近于 1 / n^logn。这个数值是非常低
的。
stable vs unstable:
通常 qsort 的实现是 unstable的，mergesort 的实现是 stable 的。
还有一点，qsort 一般是 inplace 的，mergesort 一般的实现不是 inplace 的。
random access:
qsort 要求可以对排序对象进行 random access。对于排序主内存中的 array 就很实
用。但是，遇到排序的对象不支持 random access，那么 qosrt 就不行了。比如排序
linked list，或者做磁盘文件排序。。利用这一点，可以很容易的用 mergesort 实现
并发排序。 |
