w******g 发帖数: 67 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: wyizhang (MM), 信区: JobHunting
标 题: 哪位大写给说说 何时用 merge sort, 何时用 heap sort, 何时用 quick sort?
发信站: BBS 未名空间站 (Mon Aug 23 19:59:19 2010, 美东)
刚开始看书,理解不够深刻,哪位大侠给科普一下。
1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢?
2. 看到以前有例子说n非常大的话用merge sort,几台机器分别sort,然后再merge,
这是为什么
呢?merge sort 不是需要而外的空间~n 吗?这时候用quicksort 会不会好一些?
多谢。 | g*****g 发帖数: 34805 | 2 Quicksort is an internal sorting algorithm, typically you have
to put the entire arrary in memory. Also, QS can be as slow as
O(N^2) in worst case. Merge sort normally is slower than QS
for a random array, but external sort is possible.
sort?
【在 w******g 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: wyizhang (MM), 信区: JobHunting : 标 题: 哪位大写给说说 何时用 merge sort, 何时用 heap sort, 何时用 quick sort? : 发信站: BBS 未名空间站 (Mon Aug 23 19:59:19 2010, 美东) : 刚开始看书,理解不够深刻,哪位大侠给科普一下。 : 1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢? : 2. 看到以前有例子说n非常大的话用merge sort,几台机器分别sort,然后再merge, : 这是为什么 : 呢?merge sort 不是需要而外的空间~n 吗?这时候用quicksort 会不会好一些? : 多谢。
| X****r 发帖数: 3557 | 3 一般来说quick sort就好,只有在要保证最坏情况也是O(n*log(n))下才用heap sort。
merge虽然需要O(n)的额外空间,但是并不需要这个空间同时在内存里。换句话说
它的输入输出都是顺序读写的,而不是随机读写的。
sort?
【在 w******g 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: wyizhang (MM), 信区: JobHunting : 标 题: 哪位大写给说说 何时用 merge sort, 何时用 heap sort, 何时用 quick sort? : 发信站: BBS 未名空间站 (Mon Aug 23 19:59:19 2010, 美东) : 刚开始看书,理解不够深刻,哪位大侠给科普一下。 : 1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢? : 2. 看到以前有例子说n非常大的话用merge sort,几台机器分别sort,然后再merge, : 这是为什么 : 呢?merge sort 不是需要而外的空间~n 吗?这时候用quicksort 会不会好一些? : 多谢。
| z****e 发帖数: 2024 | 4 list, forward backward access: merge sort
vector, random access: quick sort
right?
【在 X****r 的大作中提到】 : 一般来说quick sort就好,只有在要保证最坏情况也是O(n*log(n))下才用heap sort。 : merge虽然需要O(n)的额外空间,但是并不需要这个空间同时在内存里。换句话说 : 它的输入输出都是顺序读写的,而不是随机读写的。 : : sort?
| d***q 发帖数: 1119 | 5 merge sort usually is useful when dealing with a large dataset which is
unable to be loaded into memory at once.. | r*********r 发帖数: 3195 | 6 in STL, stable_sort() is merge sort. it's O(n*logn) when extra memory is
available, but O(n*(logn)^2) when not using extra memory.
STL's sort() is quick sort with some twists, it switches to heap sort when
the recursion depth is high, and uses insertion sort for small chunks.
sometimes this hybrid algorithm is called "introspective sort".
quick sort's performance heavily depends on how to pick the pivot. |
|