作者LPH66 (凉宫春日症候群)
看板Prob_Solve
标题Re: [闲聊] 阿...Merge sort
时间Mon Dec 4 21:53:51 2006
※ 引述《netsphere (5 + 3)》之铭言：
: 我想大家都写过 Merge sort
: 小弟我现在大二正在上 资料结构&演算法 的课
: 现在在教排序法 而教我们的天才教授要我们
: 写能排序Linked-list的Merge sort.....
: 天阿...有谁会想用 Merge sort 来排序Linked-list
: 怎麽想都觉得 Insert sort 比较适合来排序Linked-list
: 而且用Merge sort来排序Linked-list 程式难写 效能也低.....
: 真不知道它到底在想什麽.......
: P.S 他会要求用Linked-list是因为说Array只能事先设定固定大小
: 真怀疑它到底会不会动态记忆体配置.....
其实我觉得Linked-list的Merge sort还比较符合我们对Merge sort的直觉...
你就把两串排好的linked-list看成两堆排好的扑克牌
然後一次各拿一个node(一张牌)比较 谁小谁就放进结果串
最後形成的那一串就是排好的linked-list
而且也省空间:
这样额外花的空间只是堆叠空间而已
计入把阵列转成linked-list的空间的话也只有O(n) (以及O(log n)的递回堆叠空间)
如果用阵列传递回的话 那麽总额外空间是O(n log n) (O(log n)层 每层使用O(n))
--
'Oh, Harry, dont't you
see?' Hermione breathed. 'If she could have done
one thing to make
absolutely sure that every single person in this school
will read your interview, it was
banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 192.192.197.115
1F：推 netsphere:是没错拉 ~ 不过效能就变很慢 而且重点是程式好难写Orz 12/04 21:59
2F：推 ledia:我也同意这篇的说法, linked list 直觉得多吧 12/04 22:52
3F：→ ledia:会觉得难写是缺乏 data structure 的训练喔 :P 12/04 22:53
4F：→ ledia:不过最後说的 用阵列传不是只传一个阵列头的指标吗? 12/04 22:54
5F：推 cplusplus:难不难写看个人 还有本来就比较直觉 也不需额外空间 12/05 00:16
6F：→ cplusplus:到底哪里不好呢?? 12/05 00:16
7F：→ netsphere:程式执行比较慢阿~ 12/05 00:27
8F：推 LPH66:嗯 我所谓的总额外空间是指每层多一块出来放合并後结果 12/05 02:04
9F：→ LPH66:不过现在仔细想想好像最多不到nlogn的样子...好像只有O(n) 12/05 02:09
10F：推 cplusplus:真要讲的话，复制元素的负担也得考虑，不一定会比较慢 12/06 00:58
11F：推 cplusplus:排ARRAY要额外O(N)空间，排LIST只要O(1) 12/06 01:02
12F：推 moonshade:merge sort本来就是用linklist比较好做... 12/07 18:19
13F：→ moonshade:data structure 观念不够+1 12/07 18:20
14F：→ moonshade:用list少掉了insert的搬移... 12/07 18:21