PTT數位生活區 / Programming

[問題] MergeSort內實作sort可以用別的sort嗎?

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