在日常生活中，我們整理撲克牌時，通常會將新摸到的牌插入到手中已有牌的正確位置，使手中的牌始終保持有序。這種”逐個插入到有序部分”的思路，正是插入排序算法的核心思想。
插入排序的基本思路¶
插入排序（Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是：將數組中的元素逐個插入到已排序的子數組中，最終使整個數組達到有序狀態。具體步驟如下：
- 初始狀態：默認數組的第一個元素已經是”有序的”（只有一個元素的數組自然有序）。
- 逐個處理後續元素：從數組的第二個元素（索引1）開始，將每個元素視爲”待插入元素”。
- 尋找插入位置：將待插入元素與已排序子數組中的元素從後往前比較，找到合適的位置後插入，確保插入後子數組仍然有序。
- 重複過程：直到所有元素都被插入到正確位置，排序完成。
算法實現步驟¶
以數組 [5, 2, 9, 1, 5, 6] 爲例，詳細說明插入排序的過程：
- 外層循環：從第二個元素（索引1）開始遍歷數組，每次取出待插入元素
temp = arr[i]。 - 內層循環：從當前元素的前一個位置（
j = i-1）開始，與temp比較：
- 如果已排序子數組中的元素arr[j] > temp，則將arr[j]後移一位（arr[j+1] = arr[j]）。
- 繼續向前比較（j -= 1），直到找到arr[j] <= temp或j < 0（所有元素都比temp大）。 - 插入元素：將
temp插入到j+1的位置（確保插入後子數組有序）。
Python代碼實現¶
def insertion_sort(arr):
# 外層循環：從第二個元素開始（索引1）
for i in range(1, len(arr)):
temp = arr[i] # 保存當前待插入的元素
j = i - 1 # 從已排序子數組的末尾開始比較
# 內層循環：尋找插入位置，同時後移元素
while j >= 0 and arr[j] > temp:
arr[j + 1] = arr[j] # 當前元素後移一位
j -= 1 # 繼續比較前一個元素
arr[j + 1] = temp # 插入temp到正確位置
return arr
# 測試代碼
if __name__ == "__main__":
test_arr = [5, 2, 9, 1, 5, 6]
print("排序前：", test_arr)
sorted_arr = insertion_sort(test_arr)
print("排序後：", sorted_arr)
代碼執行示例¶
以 [5, 2, 9, 1, 5, 6] 爲例，逐步拆解排序過程：
-
i=1（待插入元素=2）：
-temp=2，j=0，arr[0]=5>2→arr[1]=5（數組變爲[5,5,9,1,5,6]），j=-1。
- 插入temp到j+1=0→ 數組變爲[2,5,9,1,5,6]。 -
i=2（待插入元素=9）：
-temp=9，j=1，arr[1]=5<=9→ 循環終止，插入位置j+1=2，數組不變。 -
i=3（待插入元素=1）：
-temp=1，j=2，arr[2]=9>1→arr[3]=9（數組變爲[2,5,9,9,5,6]），j=1。
-arr[1]=5>1→arr[2]=5（數組變爲[2,5,5,9,5,6]），j=0。
-arr[0]=2>1→arr[1]=2（數組變爲[2,2,5,9,5,6]），j=-1。
- 插入temp到j+1=0→ 數組變爲[1,2,5,9,5,6]。 -
後續步驟：繼續處理剩餘元素（5和6），最終數組變爲
[1,2,5,5,6,9]。
複雜度分析¶
- 時間複雜度：
- 最好情況（數組已排序）：O(n)（每個元素只需比較一次）。
- 最壞情況（數組逆序）：O(n²)（每個元素需比較n次）。
- 空間複雜度：O(1)（僅需一個臨時變量
temp，原地排序）。
插入排序適用於小規模數據或基本有序的數據，實現簡單且穩定。通過理解”逐個插入”的核心思想，你能輕鬆掌握這一經典排序算法的實現邏輯。