[課業] 102關務-資料結構 第四題
(如果覺得問題太沒程度,私希望各位大大鞭小力點)
題目如下:
四、考慮排序(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
推
08/16 19:35, , 1F
08/16 19:35, 1F
→
08/16 19:37, , 2F
08/16 19:37, 2F
推
08/16 19:39, , 3F
08/16 19:39, 3F
謝Lexus大!!小弟查到merge sort常用於外部排序方面的資訊了
※ 編輯: onlyu0402 (219.68.158.243), 08/16/2016 20:15:46