由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 哪位大侠给说说 何时用 merge sort, 何时用 quick sort, 何时
相关主题
underlying sort algorithm for SET in STL?如何sort and merge n 个sorted linked list
嵌入式系统用什么sorting算法比较好?一道MS面试题 (转载)
请教一个初级算法问题 (转载)我写的quick sort
问一个基本的查找问题问一个严肃的实用问题
算法之极弱问百度面试题,any idea?
我也来一个, quick sort 只要一行。两行quicksort,不难些吧
A STL sorting algorithm problem求教:多个有序数组怎么合并最快?
又一个算法题问几个关于hash, map, set的问题 (转载)
相关话题的讨论汇总
话题: sort话题: merge话题: 何时话题: quick话题: memory
进入Programming版参与讨论
1 (共1页)
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.
1 (共1页)
进入Programming版参与讨论
相关主题
问几个关于hash, map, set的问题 (转载)算法之极弱问
How to sort a map in C++ STL based on Value, instead of Key我也来一个, quick sort 只要一行。
修改map的键值A STL sorting algorithm problem
请教一个组合的算法又一个算法题
underlying sort algorithm for SET in STL?如何sort and merge n 个sorted linked list
嵌入式系统用什么sorting算法比较好?一道MS面试题 (转载)
请教一个初级算法问题 (转载)我写的quick sort
问一个基本的查找问题问一个严肃的实用问题
相关话题的讨论汇总
话题: sort话题: merge话题: 何时话题: quick话题: memory