Insertion Sort插入排序

01為什麼需要它

看到這些關鍵字就想到它：小陣列（幾十個以內）、幾乎有序、每個元素離正確位置不遠、資料一筆一筆來且要隨時有序、需要穩定又原地、混合排序的小段落。

02核心概念

插入排序就是整理手上撲克牌的方式：左手拿著一疊已經排好的牌，每次摸一張新牌，從右往左找到它該在的位置插進去。放到陣列上，就是把陣列分成左邊的已排序區 a[0..i-1] 和右邊還沒處理的部分。每一輪把 a[i] 存進 key，原位置就空出一個「洞」；往左看，比 key 大的元素一個個往右挪一格，洞跟著往左移，碰到第一個不比 key 大的元素（或到了最左邊）就停，把 key 放進洞裡。

正確性靠一個迴圈不變量：第 i 輪開始前，a[0..i-1] 恰好是原本前 i 個元素排好的結果。這一輪被挪動的都是比 key 大的元素，而且整段一起右移、彼此順序不變；停下來的位置 j 滿足 a[j] ≤ key，它左邊的元素又都 ≤ a[j]，所以 key 放進 j+1 後，a[0..i] 仍然有序。做到 i = n−1，整個陣列就排好了。因為只在嚴格大於時才挪，key 永遠不會越過和它相等的元素，所以插入排序是穩定的；而且只多用一個暫存變數，是原地排序。

複雜度看挪動次數就好：每挪一次，恰好消掉一個逆序對（key 和被它越過的元素），所以總挪動次數等於陣列的逆序對數 I；每一輪最多再多一次「不成立」的比較，比較次數介於 I 和 I + (n−1) 之間，總時間是 O(n + I)。已排序時 I = 0，只做 n−1 次比較，最好 O(n)；完全反序時 I = n(n−1)/2，最壞 O(n²)；隨機資料的逆序對期望值是 n(n−1)/4，平均仍是 O(n²)。若每個元素離最終位置最多 k 格，每個元素最多往左挪 k 格，時間就是 O(nk)。額外空間 O(1)。

常見的錯有三個。迴圈條件必須有 j >= 0，而且要寫在 a[j] > key 前面：C++ 少了它或順序反了，會讀到 a[-1] 這個越界位置；Python 的 a[-1] 是合法的「最後一個元素」，少了檢查可能丟出 IndexError，也可能不報錯卻把資料弄亂。把 > 寫成 >= 會讓相等元素互相越過，失去穩定性。用交換代替挪動結果一樣，但每一步從一次寫入變成三次，做的其實就是氣泡排序那種相鄰交換。和鄰居比較：氣泡排序的交換次數同樣等於逆序對數，但插入排序每步只寫一次；選擇排序不管資料長怎樣都要 n(n−1)/2 次比較，插入排序則會隨資料越有序而自動變快（自適應）。它也是線上演算法，資料一筆一筆到也能維持有序。合併排序、快速排序在小段落改用它；把「挪一格」推廣成「挪 gap 格」，就是希爾排序。

03演算法步驟

1. 1外層 i 從 1 跑到 n−1。進入第 i 輪時，a[0..i-1] 已經有序；一開始只有 a[0]，一個元素自己就是有序的。
2. 2把 a[i] 存進 key，令 j = i − 1。此時 a[i] 可以視為一個洞，覆寫它不會弄丟資料。
3. 3while j >= 0 and a[j] > key：a[j+1] = a[j]，j -= 1。先檢查 j >= 0，而且只在嚴格大於時挪，才能保持穩定。
4. 4迴圈停下時 a[j] ≤ key 或 j = −1，把 key 寫進 a[j+1]，已排序區變成 a[0..i]。
5. 5比較很貴時，改用 bisect_right（upper_bound）在 a[0..i-1] 找插入位置，再整段右移；當作混合排序的小段落使用時，把左界 0 換成區段起點 lo。

04互動示範

共用陣列 [5, 2, 9, 1, 7, 3, 8, 4]。每一輪拿起一個元素放到「手上的牌」，原位置變成虛線的洞；綠色是已排序區，黃色是剛和手上的牌比較過的元素（比較大就挪到右邊一格，洞往左移），藍色是剛插入的位置。注意插入 9 時只比一次就停下，插入 1 則一路挪到最左邊；最後挪動次數是 13，正好是這個陣列的逆序對數量。比較是 18 次：13 次挪動，加上 5 次讓迴圈停下的比較（插入 2 和 1 時到了最左邊才停，不需要這一次），正好落在 I 到 I + (n−1) = 20 之間。

05程式碼

基本版加上兩個變形。二分插入排序把比較次數降到 O(n log n)，但搬移仍是 O(n²)，適合比較很貴的字串或物件，Timsort 用的就是它；C++ 用 std::upper_bound 找位置、std::rotate 一次挪整段。區間版只排 a[lo..hi]，是混合排序在小段落呼叫的形式。

from bisect import bisect_right


# 插入排序：左邊 a[0..i-1] 已排好，拿起 a[i]，比它大的往右挪，再放進洞裡
def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]                          # 手上的牌，a[i] 變成洞
        j = i - 1
        while j >= 0 and a[j] > key:        # 嚴格大於才挪，同值不越過，保持穩定
            a[j + 1] = a[j]                 # 往右挪一格，洞往左移
            j -= 1
        a[j + 1] = key                      # 放進洞裡
    return a


# 變形一：二分插入排序
# 用二分搜尋找位置，比較降到 O(n log n)；搬移仍是 O(n²)，適合比較很貴的資料
def binary_insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        pos = bisect_right(a, key, 0, i)    # 放在相等元素的右邊，保持穩定
        a[pos + 1:i + 1] = a[pos:i]         # 整段往右挪一格
        a[pos] = key
    return a


# 變形二：只排 a[lo..hi]（閉區間）
# 混合排序切到小段時呼叫它，而不是繼續遞迴
def insertion_sort_range(a, lo, hi):
    for i in range(lo + 1, hi + 1):
        key = a[i]
        j = i - 1
        while j >= lo and a[j] > key:       # 左界是 lo，不是 0
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key


if __name__ == "__main__":
    print(insertion_sort([5, 2, 9, 1, 7, 3, 8, 4]))                  # [1, 2, 3, 4, 5, 7, 8, 9]
    print(binary_insertion_sort(["pear", "fig", "apple", "kiwi"]))  # ['apple', 'fig', 'kiwi', 'pear']
    b = [9, 8, 7, 6, 5, 4, 3, 2, 1]
    insertion_sort_range(b, 2, 6)                                    # 只排索引 2..6
    print(b)                                                         # [9, 8, 3, 4, 5, 6, 7, 2, 1]

06練習題

• LeetCode 2418Sort the People（手寫插入排序，名字跟著身高一起挪）Easy
• LeetCode 147Insertion Sort List（鏈結串列不用挪，但要從頭找位置）Medium
• LeetCode 57Insert Interval（在有序區間裡找位置插入，再合併重疊）Medium
• LeetCode 775Global and Local Inversions（每個元素離定位最多 1 格時，逆序對全是相鄰的）Medium
• LeetCode 1649Create Sorted Array through Instructions（每次插入的成本，要用 BIT 加速）Hard