插入排序法（Insertion Sort）利用陣列中相鄰元素的交換（Swap）動作對n 個數字排序。在不同輸入（Input）的情況下，其交換次數以複雜度（Com…

題目

插入排序法（Insertion Sort）利用陣列中相鄰元素的交換（Swap）動作對n 個數字排序。在不同輸入（Input）的情況下，其交換次數以複雜度（Complexity）而言最少及最多者為何？ A. 最少：Θ(n)，最多：Θ(n2) B. 最少：Θ(n2)，最多：Θ(n2) C. 最少：Θ(n)，最多：Θ(n log n) D. 最少：Θ(n log n)，最多：Θ(n log n)

官方答案

• 答案：A. 最少：Θ(n)，最多：Θ(n2)

解析

插入排序逐一取出元素，插入前方已排序的部分。若輸入已由小到大排列，每個元素只需與前一個比較一次即可就位，整體只需線性次數 Θ(n)；若輸入反向排列，第 i 個元素必須往前移動 i 次，總交換次數為 1+2+…+(n-1)=n(n-1)/2，屬於 Θ(n²)。因此交換次數最少為 Θ(n)、最多為 Θ(n²)。Θ(n log n) 是合併排序、堆積排序等比較式排序的級別，並非插入排序的交換次數。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。