作者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