一、從整理撲克牌說起¶
想象一下，你剛拿到一副打亂的撲克牌，比如：5, 3, 8, 4, 2。現在你想把它們從小到大排好序，應該怎麼做？
最直觀的方法可能是這樣的：先挑出一張牌（比如第一張5）作爲“已排好序的牌堆”，然後依次拿起剩下的牌，每張牌都插入到已排好序的牌堆中合適的位置。
- 第一步：先理出第一張牌5，已排序牌堆：
[5] - 第二步：拿起第二張牌3，發現3比5小，所以插入到5前面，已排序牌堆變成：
[3, 5] - 第三步：拿起第三張牌8，8比5大，直接放到已排序牌堆末尾，變成：
[3, 5, 8] - 第四步：拿起第四張牌4，需要和已排序牌堆的最後一張牌8比較，4 < 8，所以繼續往前比較5，4 < 5，再比較3，4 > 3，所以插入到3和5之間，已排序牌堆變成：
[3, 4, 5, 8] - 第五步：拿起第五張牌2，依次和8、5、4、3比較，2比所有牌都小，所以插入到最前面，最終排好序的牌堆：
[2, 3, 4, 5, 8]
這個過程是不是很熟悉？其實，這就是插入排序的核心思想——把待排序的元素逐個插入到已排序的序列中。
二、插入排序的原理¶
插入排序的邏輯可以用“逐步構建有序序列”來理解：
- 默認有序：假設第一個元素已經是“有序序列”的一部分（只有一個元素，自然有序）。
- 逐個插入：從第二個元素開始，把每個元素當作“新牌”，插入到前面已經排好序的序列中的正確位置。
- 移動元素，騰出位置：如果新牌比已排序序列中的某些牌小，需要把那些較大的牌“後移”一位，給新牌騰出位置。
三、實例演示：以數組[5, 3, 8, 4, 2]爲例¶
我們用上面的撲克牌例子，把每個步驟用數組操作來模擬：
| 步驟 | 已排序序列 | 待插入元素 | 比較過程 | 插入後序列 |
|---|---|---|---|---|
| 1 | [5] |
3（第二個元素） | 3 < 5 → 後移5 | [3, 5] |
| 2 | [3, 5] |
8（第三個元素） | 8 > 5 → 直接插入末尾 | [3, 5, 8] |
| 3 | [3, 5, 8] |
4（第四個元素） | 4 < 8 → 後移8；4 < 5 → 後移5；4 > 3 → 插入中間 | [3, 4, 5, 8] |
| 4 | [3, 4, 5, 8] |
2（第五個元素） | 2 < 8 → 後移8；2 < 5 → 後移5；2 < 4 → 後移4；2 < 3 → 後移3 | [2, 3, 4, 5, 8] |
關鍵觀察：每次插入時，待插入元素會與已排序序列中的元素從後往前比較，直到找到合適的位置。
四、算法步驟與僞代碼¶
算法步驟：¶
- 遍歷數組，從第二個元素（索引1）開始處理（記爲
i）。 - 把當前元素
arr[i]暫存爲key（待插入元素）。 - 從已排序序列的末尾開始（即
i-1），用j指向已排序元素：
- 如果arr[j] > key，則把arr[j]後移一位（arr[j+1] = arr[j]）。
- 如果arr[j] <= key，則停止移動，此時j+1就是key的插入位置。 - 將
key插入到arr[j+1]的位置。 - 繼續處理下一個元素（
i += 1），直到所有元素處理完畢。
僞代碼：¶
插入排序(arr)
對於 i 從 1 到 數組長度 - 1:
key = arr[i] // 取出待插入元素
j = i - 1 // 已排序序列的末尾索引
// 移動已排序元素，騰出位置
while j >= 0 且 arr[j] > key:
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = key // 插入待插入元素
返回 arr
五、Python代碼實現¶
def insertion_sort(arr):
# 從第二個元素開始遍歷（索引1）
for i in range(1, len(arr)):
key = arr[i] # 待插入元素
j = i - 1 # 已排序序列的末尾索引
# 移動已排序元素，直到找到插入位置
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j] # 已排序元素後移
j -= 1 # 繼續向前比較
arr[j + 1] = key # 插入待插入元素
return arr
# 測試代碼
test_arr = [5, 3, 8, 4, 2]
sorted_arr = insertion_sort(test_arr)
print("排序前：", test_arr)
print("排序後：", sorted_arr)
六、插入排序的特點¶
優點：¶
- 簡單直觀：邏輯清晰，容易理解和實現。
- 原地排序：只需要一個臨時變量（
key），空間複雜度爲 O(1)。 - 適應性強：適合“幾乎有序”的數據（比如已排好序的數組，時間複雜度接近 O(n)）。
- 穩定排序：相等元素的相對順序不會改變（如撲克牌中相同點數的牌，原順序保持不變）。
缺點：¶
- 時間複雜度高：最壞情況下（完全逆序）爲 O(n²)，不適合大規模數據。
- 移動操作多：對於每個待插入元素，可能需要多次移動已排序元素。
七、總結¶
插入排序的核心思想就像我們整理撲克牌：先把小範圍的牌排好序，再逐步擴展到整個序列。它的實現邏輯簡單，適合初學者理解排序算法的基本思路，也常用於實際開發中對小規模數據或幾乎有序數據的排序。
如果你覺得插入排序的邏輯還不夠清晰，可以試着用不同的數組（比如 [9, 7, 6, 15, 16, 5]）手動模擬排序過程，加深對“移動已排序元素”和“找到插入位置”的理解。排序算法的基礎就是從這些簡單的生活類比開始的~