Re: [閒聊] 阿...Merge sort
看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (涼宮春日症候群)時間18年前 (2006/12/04 21:48)推噓7(7推 0噓 7→)留言14則, 5人參與討論串2/6 (看更多)
※ 引述《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
推
12/04 21:59, , 1F
12/04 21:59, 1F
推
12/04 22:52, , 2F
12/04 22:52, 2F
→
12/04 22:53, , 3F
12/04 22:53, 3F
→
12/04 22:54, , 4F
12/04 22:54, 4F
推
12/05 00:16, , 5F
12/05 00:16, 5F
→
12/05 00:16, , 6F
12/05 00:16, 6F
→
12/05 00:27, , 7F
12/05 00:27, 7F
推
12/05 02:04, , 8F
12/05 02:04, 8F
→
12/05 02:09, , 9F
12/05 02:09, 9F
推
12/06 00:58, , 10F
12/06 00:58, 10F
推
12/06 01:02, , 11F
12/06 01:02, 11F
推
12/07 18:19, , 12F
12/07 18:19, 12F
→
12/07 18:20, , 13F
12/07 18:20, 13F
→
12/07 18:21, , 14F
12/07 18:21, 14F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 6 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
