推 lexus7310: 第一題寫的不夠仔細 第二題是合併排序 08/16 19:35
→ lexus7310: 合併排序的目的就是用於記憶體不足 08/16 19:37
推 lexus7310: 所以需要大量的資料搬移動作 08/16 19:39
謝Lexus大!!小弟查到merge sort常用於外部排序方面的資訊了
※ 編輯: onlyu0402 (219.68.158.243), 08/16/2016 20:15:46
(如果覺得問題太沒程度，私希望各位大大鞭小力點)
題目如下:
四、考慮排序(sort)的問題:(每小題10分，共30分)
(一)如果要排序的資料很少，例如只有十幾筆資料，那麼你將採用快速排序法(quick
sort)?合併排序法(merge sort)?還是氣泡排序法(bubble sort)?為什麼?
(二)如果要排序的資料很多，例如多到超過主記憶體容量許多，那麼你將採用快速排序
法?合併排序法?還是氣泡排序法?為什麼?
小弟擬答如下:
(一)(1)氣泡排序法。(2)雖然快速排序法與合併排序法所需的平均時間複雜度為O(nlogn)
皆優於氣泡排序法的O(n^2)，但因需要處理的資料量不大，故所實際花費時間相差不大且
氣泡排序法實作較簡單易懂。
(二)(1)氣泡排序法。(2)因為快速排序法與合併排序法皆採用divide and conquer的解法
，以遞迴的方式實作，將消耗大量記憶體空間，故若資料量過大記憶體可能不敷使用。
以上擬答中，對於第(二)題較沒把握，因為資料量大氣泡排序真的會跑很久，但題目
又提到資料多到超過記憶體容量許多...所以懇求各位先進指點一下觀念Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.68.158.243
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1471332422.A.1C8.html
※ 編輯: onlyu0402 (219.68.158.243), 08/16/2016 16:19:12