插入排序法教學：原理、程式碼與時間複雜度

用白話說明原理

把第一個元素視為長度為一的已排序串列。取出第二個元素，插到第一個的前面或後面。取出第三個元素，插到前兩個之間正確的位置。持續進行，直到每個元素都插入完畢。

要插入時，先把新元素拿在一旁（稱為 key），然後在已排序的部分中向左走。每個比 key 大的元素都往右移一格。走到一個不比 key 大的元素，或到達串列開頭時，就把 key 放進空位。

逐步範例

將 [12, 11, 13, 5, 6] 排序。直線之前的部分已排序（但還不是最終位置）。

注意第 2 步：已在正確位置的元素只需一次比較。這就是插入排序在幾乎已排序的輸入上很快的原因。

Python 實作

def insertion_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:   # strict >, keeps it stable
            items[j + 1] = items[j]        # shift right
            j -= 1
        items[j + 1] = key                 # drop into the gap
    return items
print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]
print(insertion_sort([1, 2, 3, 4]))         # [1, 2, 3, 4], 3 comparisons

用位移取代交換，每個被移動的元素只寫入一次，工作量約為交換版本的一半。你也可以像下面這樣用二分搜尋找出插入點。這能把比較次數總共降到 O(n log n)，但位移仍是 O(n²)，所以整體時間仍是 O(n²)。

from bisect import insort_right
def binary_insertion_sort(items):
    result = []
    for x in items:
        insort_right(result, x)   # stable: equal items go after
    return result
print(binary_insertion_sort([3, 1, 2, 1]))   # [1, 1, 2, 3]

時間與空間複雜度

更精確地說，執行時間是 O(n + I)，其中 I 是逆序對（順序顛倒的元素對）的數量。如果每個元素距離它的最終位置至多 k 格，I 至多為 n · k，所以插入排序是 O(n · k)：k 很小時非常快。

插入排序與其他排序法的比較

插入排序是穩定的，因為元素只會向左越過嚴格比它大的元素。它同時也是線上（online）演算法：能在資料陸續抵達時邊收邊排，隨時維持有序的前綴。對短串列來說，它的低開銷勝過 O(n log n) 的演算法，所以 Timsort（Python 使用，Java 對物件排序也用）以二分插入排序處理短的順串（run），許多快速排序的實作在子陣列小於一定大小時也會改用插入排序。

變體與常見錯誤

• 二分插入排序：用二分搜尋找出位置，再做位移。比較次數更少，在比較成本很高時有幫助。
• Shell 排序：對相隔一段間隙的元素執行插入排序，再把間隙縮小到 1。它能讓遠處的元素快速移動，在大型陣列上比單純的插入排序快得多。
• 鏈結串列的插入排序：不需要位移，但找位置仍是線性掃描。

何時使用插入排序

適用於小型陣列（幾十個元素）、幾乎已排序的資料（例如排序過後又附加了少數幾個元素的串列），以及你需要一個簡單、穩定又原地的排序法時。對大型隨機資料，請使用 O(n log n) 的排序法；在 Python 中就是 sorted() 或 list.sort()，它們內部本來就會對短的順串使用插入排序。

面試題常問追蹤過程、最佳與最差情況、為何穩定，或為何在小型與幾乎已排序的輸入上勝過 O(n log n) 的演算法。