民國108年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第16題
假設排序演算法僅能使用「比較」(Comparison)與 「對調」(Exchange)。讀入資料1,5,4,3,2,利用 插入排序法(Insertion Sor…
題目
假設排序演算法僅能使用「比較」(Comparison)與 「對調」(Exchange)。讀入資料1,5,4,3,2,利用 插入排序法(Insertion Sort)將其由小至大排序,需要多少次對調?
- (1) 5
- (2) 6
- (3) 7
- (4) 8
官方答案
(2) 6
解析
插入排序逐一把目前元素插入前面已排序的部分，過程中以相鄰對調計次。初始 1,5,4,3,2：插入 5 時 5 大於 1，不需對調（0 次）；插入 4 時與 5 對調 1 次，得 1,4,5,3,2；插入 3 時依序與 5、4 對調共 2 次，得 1,3,4,5,2；插入 2 時依序與 5、4、3 對調共 3 次，得 1,2,3,4,5。合計 0＋1＋2＋3＝6 次，故選項 2 正確，其餘數值皆與計算結果不符。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。