插入排序（Insertion Sort）

插入排序是一種簡單的排序算法。它的基本思想是：將數(shù)組分為已排序部分和未排序部分，然后逐個將未排序部分的元素插入到已排序部分的正確位置。插入排序類似于整理撲克牌的過程。

插入排序的步驟：

1. 初始化：將第一個元素視為已排序部分。
2. 插入元素：從未排序部分取出一個元素，將其插入到已排序部分的正確位置。
3. 重復過程：重復上述步驟，直到所有元素都被排序。

時間復雜度：

• 最壞情況：O(n2) —— 當數(shù)組是逆序的時候。
• 最好情況：O(n) —— 當數(shù)組已經有序的時候。
• 平均情況：O(n2)

空間復雜度：

• O(1) —— 插入排序是一種原地排序算法，不需要額外的存儲空間。

---

Python 實現(xiàn)

def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]  # 當前需要插入的元素j = i - 1# 將比 key 大的元素向后移動while j >= 0 and arr[j] > key:arr[j + 1] = arr[j]j -= 1# 將 key 插入到正確位置arr[j + 1] = keyreturn arr# 示例使用
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("排序后的數(shù)組:", sorted_arr)

---

輸出結果

排序后的數(shù)組: [5, 6, 11, 12, 13]

---

插入排序的詳細過程

以數(shù)組 [12, 11, 13, 5, 6] 為例：

1. 第一輪：

   • 已排序部分：[12]
   • 未排序部分：[11, 13, 5, 6]
   • 將 11 插入到已排序部分，數(shù)組變?yōu)?[11, 12, 13, 5, 6]。

2. 第二輪：

   • 已排序部分：[11, 12]
   • 未排序部分：[13, 5, 6]
   • 將 13 插入到已排序部分，數(shù)組變?yōu)?[11, 12, 13, 5, 6]。

3. 第三輪：

   • 已排序部分：[11, 12, 13]
   • 未排序部分：[5, 6]
   • 將 5 插入到已排序部分，數(shù)組變?yōu)?[5, 11, 12, 13, 6]。

4. 第四輪：

   • 已排序部分：[5, 11, 12, 13]
   • 未排序部分：[6]
   • 將 6 插入到已排序部分，數(shù)組變?yōu)?[5, 6, 11, 12, 13]。

5. 排序完成。

---

插入排序的優(yōu)缺點

優(yōu)點：

• 實現(xiàn)簡單，易于理解。
• 對于小規(guī)模數(shù)據或基本有序的數(shù)據，效率較高。
• 是穩(wěn)定的排序算法（相同元素的相對位置不變）。

缺點：

• 時間復雜度較高，不適合處理大規(guī)模數(shù)據。
• 對于逆序數(shù)據，性能較差。

---

插入排序的適用場景

• 數(shù)據規(guī)模較小。
• 數(shù)據基本有序。
• 需要穩(wěn)定排序的場景。