寄托家园留学论坛 › 论坛 › 寄托学术类备考版 › GRE考试综合版 › GRE_SUB › CS SUB Test Taker phoenixinter报到

返回列表

楼主: phoenixinter

[未归类] CS SUB Test Taker phoenixinter报到 [复制链接]

phoenixinter
UID: 2161191

等待验证会员

声望: 0
寄托币: 12
注册时间: 2012-8-20
精华: 0
帖子: 9

16楼

发表于 2006-11-1 08:36:11 |只看该作者

回复 #11 vaughen 的帖子

heapsort是sort in place的
所有O(n^2)的排序都是稳定的
所有O(nlogn)的排序除了mergesort是稳定的其它都是不稳定的

使用道具举报

realyoyy
UID: 2198700

中级会员

Rank: 4

声望: 0
寄托币: 516
注册时间: 2006-3-19
精华: 1
帖子: 6

17楼

发表于 2006-11-1 13:04:11 |只看该作者

但是那個pdf上說
Method Complexity BestCase  WorstCase    Sort in place
Insertion O(n2)                                              Yes
Selection  O(n2)                                              No
Bubble    O(n2)                                           Yes
Quick    O(nlogn)                                        No
Heap       O(nlogn)                                        Yes
Merge       O(nlogn)                                           Yes
Shell       O(nlogn)                                        No

大家看看有錯麽？
另外到底什麽是sort in place

双非DIY美硕申请总结

使用道具举报

realyoyy
UID: 2198700

中级会员

Rank: 4

声望: 0
寄托币: 516
注册时间: 2006-3-19
精华: 1
帖子: 6

18楼

发表于 2006-11-1 13:08:49 |只看该作者

in-place sort

Definition: A sort algorithm in which the sorted items occupy the same storage as the original ones. These algorithms may use o(n) additional memory for bookkeeping, but at most a constant number of items are kept in auxiliary memory at any time.

Also known as sort in place.

Specialization (... is a kind of me.)
American flag sort, quicksort, insertion sort, selection sort, Shell sort, diminishing increment sort, J sort, gnome sort.

使用道具举报

realyoyy
UID: 2198700

中级会员

Rank: 4

声望: 0
寄托币: 516
注册时间: 2006-3-19
精华: 1
帖子: 6

19楼

发表于 2006-11-1 13:11:27 |只看该作者

網上搜索一下和那個網上的CSSUB pdf 很多矛盾（quick,selection,shell)阿
大家討論一下

使用道具举报

十指飞舞
UID: 2228487

寄托新兵

Rank: 2

声望: 0
寄托币: 290
注册时间: 2006-7-9
精华: 0
帖子: 2

20楼

发表于 2006-11-1 14:34:04 |只看该作者

原帖由 realyoyy 于 2006-11-1 13:04 发表
但是那個pdf上說
Method Complexity BestCase  WorstCase    Sort in place
Insertion O(n2)                                              Yes
Selection  O(n2)                               ...

这个书还是有不少错误的
最好对照一下教材

使用道具举报

phoenixinter
UID: 2161191

等待验证会员

声望: 0
寄托币: 12
注册时间: 2012-8-20
精华: 0
帖子: 9

21楼

发表于 2006-11-2 09:25:04 |只看该作者

回复 #20 十指飞舞的帖子

确实
反正我说的肯定是对的
你们相信就是-__

使用道具举报

yt_May
UID: 209423

寄托新兵

Rank: 2

声望: 0
寄托币: 149
注册时间: 2005-5-7
精华: 0
帖子: 1

22楼

发表于 2006-11-2 13:15:12 |只看该作者

原帖由 realyoyy 于 2006-11-1 13:08 发表
in-place sort

Definition: A sort algorithm in which the sorted items occupy the same storage as the original ones. These algorithms may use o(n) additional memory for bookkeeping, but at most a ...

这个是正解~

使用道具举报

xiaoyouyou
UID: 2195100

新手上路

Rank: 1

声望: 0
寄托币: 59
注册时间: 2006-3-9
精华: 0
帖子: 0

23楼

发表于 2006-11-3 16:35:31 |只看该作者

你可以说heap是sort in place 也可以说不是，这个不会细考的，因为heap排序的原理就是先搞成max heap 或min heap，然后一次次的取root来排，如果你将heap按 level顺序放在数组里，每次取出的root扔到这个数组后面，那就是 in place sort, 你要非用另外一个数组存放，那就不算，我记得当年学这个的时候老师讲的很明白，那本英文原版书也写得很明白，大家不要争了

使用道具举报