插入排序 (Insertion Sort) 也是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。

演算法步驟

1. 從第二個元素開始，將該元素與前面的元素進行比較。
2. 如果該元素比前面的元素小，則將前面的元素往後移動一位。
3. 重複步驟2，直到找到該元素應插入的位置。
4. 將該元素插入到正確的位置。
5. 重複步驟1~4，直到所有元素都排序完成。

範例

假設有一個陣列 $A = [5, 2, 4, 6, 1, 3]$，插入排序的過程如下:

程式碼範例

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 測試
print(insertion_sort([5, 2, 4, 6, 1, 3]))

複雜度分析

• 最佳情況：$O(n)$（已排序）
• 最壞情況：$O(n^2)$（反向排序）
• 穩定性：穩定排序

優缺點

結語

插入排序雖然與氣泡排序、選擇排序一樣屬於 O(n^2) 的基礎排序演算法，但它的特性更貼近「人類整理資料」的直覺思維：就像整理撲克牌一樣，每次抽一張牌，插入到已經排好的手牌中。

它的最大優勢在於:

• 小型資料集: 程式碼簡單、常數因子小，在十幾筆甚至數十筆資料時，表現往往不輸更複雜的演算法。
• 近乎有序的資料: 最佳情況下僅需一次掃描，時間複雜度可降到 O(n)，非常高效。
• 穩定性: 插入排序是穩定排序，能保證相同元素的相對順序不被破壞。

不過它的瓶頸也很明顯：在大型或高度無序的資料上，仍然需要大量比較與移動，最壞情況下的複雜度依然是 O(n^2)。因此，在真實應用中，插入排序常被用於:

• 教學用途，幫助初學者理解排序與資料移動的直觀過程；
• 作為高效排序演算法 (例如快速排序、Timsort) 的子程序，專門處理小規模或幾乎有序的子區間，提升整體效能。

總體來說，插入排序是「簡單但不容忽視」的演算法。雖然它不是解決大型問題的最佳選擇，但它在小規模場景或混合演算法設計中，依然有獨特的價值。