申論題 - 阿摩線上測驗

申論題資訊

試卷：106年 - 106 經濟部所屬事業機構_新進職員甄試_資訊：1.資訊管理、2.程式設計#69345
科目：國營事業◆1.資訊管理 2.程式設計
年份：106年
排序：0

六、【表 2】是某籃球隊 10 位隊員參加 2 場比賽的得分統計表，在考慮平均執行時間的前提下，請以內部排序法中最好的方法，回答下列問題。（25 分） php4xJehu

(一)欲將 2 場比賽各隊員的總得分由小至大排列完成，請寫出此排序法為何（3 分）？並說明此排序的作法（7 分）。

詳解提供者：abaochang

內部排序(Internal Sort)
資料筆數少，可以全部放到記憶體中排序
一般的演算法皆為內部排序
外部排序(External Sort)
資料量大，無法放到記憶體中排序，需透過其它儲存裝置輔助
外部排序通常會分次載入部份的資料到記憶體，用內部排序演算法排序後再回存或合併結果

詳解提供者：我還有明天

考慮平均時間最有效率的情況下

可選擇合併排序法

其時間複雜度為O(nlogn)

排序步驟：

1.將陣列依照個數一分為二

2.重複第1步驟，直到陣列細分到僅剩一個數值

3.兩兩比較後排序並合併為一個較大數列

4.重複第3步驟直到完成所有數字排序成一個陣列

以第2場得分陣列為例

（開始分割）

10、3、20、1、31、6、22、5、26、14

10、3、20、1、31｜6、22、5、26、14

10、3｜20、1、31 6、22｜5、26、14

10、3 20、1｜31 6、22 5、26｜14

10｜3 20｜1 31 6｜22 5｜26 14

10 3 20 1 31 6 22 5 26 14

（開始合併）

3、10 1、20 31 6、22 5、26 14

3、10 1、20、31 6、22 5、14、26

1、3、10、20、31 5、6、14、22、26

1、3、5、6、10、14、20、22、26、31