Re: [閒聊] 阿...Merge sort

看板Prob_Solve作者LPH66 (涼宮春日症候群)時間17年前 (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

推

netsphere

12/04 21:59, , 1^F

12/04 21:59, 1^F

推

ledia

12/04 22:52, , 2^F

12/04 22:52, 2^F

→

ledia

12/04 22:53, , 3^F

12/04 22:53, 3^F