初考-統計資料處理大意109 年第 20 題單選題
關於插入排序法（insertion sort）的描述，何者錯誤？
A最糟情況的複雜度是 n log n正確答案
B最佳情況的複雜度是 n
C適用於順序錯誤較少的資料排序
D可以和 quick sort 合作以提升 quick sort 排序速度
A正確答案
插入排序最糟情況複雜度是 O(n²)，不是 O(n log n)，後者是快速/合併排序的平均複雜度。
為什麼答案是 A
錯誤敘述（即本題要選的答案）。插入排序最糟情況發生在資料完全逆序時，需比較與搬移 n(n-1)/2 次，複雜度為 O(n²)，不是 O(n log n)。
載入中…
完整詳解
Pro · 無限重點 插入排序最糟情況複雜度是 O(n²)，不是 O(n log n)，後者是快速/合併排序的平均複雜度。
記住：插入、氣泡、選擇排序最糟都是 O(n²)；只有分治類（quick/merge/heap）才到 O(n log n)。
逐選項分析
A✓ 正確
錯誤敘述（即本題要選的答案）。插入排序最糟情況發生在資料完全逆序時，需比較與搬移 n(n-1)/2 次，複雜度為 O(n²)，不是 O(n log n)。
B✕
正確。當資料已排序好時，每個元素只需與前一個比較一次即可確認位置，總比較次數為 n-1，複雜度為 O(n)。
C✕
正確。插入排序對「接近已排序」的資料效率極佳，因為大部分元素幾乎不用移動，是其最大優勢。
D✕ 陷阱
正確。實務上 quick sort 在小區段（如長度 < 10）改用 insertion sort 可減少遞迴負擔，這是 introsort 等混合排序的常見設計。
常見排序法複雜度總覽
| 演算法 | 最佳 | 平均 | 最糟 |
|---|
| 插入排序 Insertion | O(n) | O(n²) | O(n²) |
| 氣泡排序 Bubble | O(n) | O(n²) | O(n²) |
| 選擇排序 Selection | O(n²) | O(n²) | O(n²) |
| 快速排序 Quick | O(n log n) | O(n log n) | O(n²) |
| 合併排序 Merge | O(n log n) | O(n log n) | O(n log n) |
| 堆積排序 Heap | O(n log n) | O(n log n) | O(n log n) |
命題者把 O(n log n) 偷偷塞到插入排序的最糟情況，這其實是快速/合併排序的複雜度。考生若沒背熟排序表，容易誤以為「最糟都差不多」而放過 A 選項。 
