插入排序法（Insertion Sort）利用陣列中相鄰元素的交換（Swap）動作對 n 個數字排序。在不同輸入（Input）的情況下，其交換次數以複雜度（Complexity）而言最少及最多者為何？
A最少：Θ(n)，最多：Θ(n²)正確答案
B最少：Θ(n²)，最多：Θ(n²)
C最少：Θ(n)，最多：Θ(n log n)
D最少：Θ(n log n)，最多：Θ(n log n)
答案與詳解
為什麼答案是 A
最佳情況輸入已排序，每個元素只需比較一次不需交換，總執行時間 Θ(n)；最差情況輸入逆序，第 i 個元素需交換 i-1 次，總交換次數為 n(n-1)/2，屬 Θ(n²)。
考點：插入排序複雜度考點：最佳情況誤判考點：排序法混淆考點：演算法分類錯置
載入中…
