作者KAINTS (Faith)
看板Programming
標題[問題] MergeSort內實作sort可以用別的sort嗎?
時間Sun Apr 4 21:00:03 2021
請問各位大大好最近小弟在寫一些sort的練習
我想請教一下 MergeSort內分為兩個階段
1.Divide (分割)
2.Conquer (合併)
小弟在寫合併的時候
有一個問題覺得困惑
因為conquer時必須要把序列sort過
那麼我在這個時候去調用別的sort這樣也可以嗎?
比方說我sort的方式是用quick sort
這樣會影響這個演算法本身的時間複雜度?
我的認知是不會 畢竟我們都已經經過divied的了
所以基本上就是O(logn)
不知道我這樣理解對嗎?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.222.216 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Programming/M.1617541205.A.B5C.html
1F：推 alan23273850: mergesort 精華就是可以一直 divid 111.83.155.49 04/05 00:48
2F：→ alan23273850: e，如果還要調用其他 sort 的話那 111.83.155.49 04/05 00:48
3F：→ alan23273850: 幹嘛還要 divide 111.83.155.49 04/05 00:48
4F：→ alan23273850: 你時間當然就是 qs(n/2) + O(n) 111.83.155.49 04/05 00:50
5F：→ alan23273850: 更正，2 * qs(n/2) + O(n) 111.83.155.49 04/05 00:51
6F：推 LPH66: 這裡有個概念叫做遞迴, 你分割後得到了兩個 180.177.0.237 04/05 01:02
7F：→ LPH66: 同樣需要排序但數量變少的陣列 180.177.0.237 04/05 01:02
8F：→ LPH66: 那你就可以遞迴呼叫自己進行排序 180.177.0.237 04/05 01:03
9F：→ LPH66: 數量變少這個條件會保證你能切到剩一個 180.177.0.237 04/05 01:03
10F：→ LPH66: ==== 180.177.0.237 04/05 01:06
11F：→ LPH66: 但是, 如果你的焦點只想擺在合併步驟的話 180.177.0.237 04/05 01:06
12F：→ LPH66: 你已經不是在用合併排序法, 而只是單純地 180.177.0.237 04/05 01:07
13F：→ LPH66: 把兩個已排序的陣列合成一個排序陣列 180.177.0.237 04/05 01:07
14F：→ LPH66: 合併排序法需要這個合併步驟但這不是全部 180.177.0.237 04/05 01:07
感謝兩位大大指導
但我是已經確定把分割做到最後了只剩一個
我只是想說在合併的時候使用While去合併數列 不如直接套用其他Sort來加速
看來這樣想法有錯 感謝感謝
※ 編輯: KAINTS (122.116.222.216 臺灣), 04/05/2021 09:01:17
15F：推 LPH66: 那正好會適得其反; 合併步驟只有線性才能 180.177.0.237 04/05 16:21
16F：→ LPH66: 得到整個演算法是 O(n log n) 180.177.0.237 04/05 16:21
17F：→ LPH66: 如果你的合併步驟是 O(n log n) 180.177.0.237 04/05 16:22
18F：→ LPH66: 則整個演算法會變成 O(n (log n)^2) 180.177.0.237 04/05 16:22
19F：→ LPH66: 反而稍微地變慢了 180.177.0.237 04/05 16:22