Insertion Sort(插入排序法)
介紹
工作原理：
- 初始化：將第一個元素視為已排序的部分。
- 逐步插入：從第二個元素開始，將其與已排序部分中的元素進行比較。
- 重複：重複上述步驟，直到所有元素都被插入到正確的位置。
排序過程示例
假設有一串數字：
- 第一輪：取出
，放到已排序的部分 ，不需移動，保持不變。 - 第二輪：已排序部分為
，取出 ，將 插入到 之前，變為 。 - 第三輪：已排序部分為
，取出 ，因為 大於 ，不需移動，保持不變。 - 第四輪：已排序部分為
，取出 ，放到已排序的最前面，變為 。 - 第五輪：已排序部分為
，取出 ，將 插入到 之前。 - 最終結果為
。
範例程式碼
python
def insertion_sort(arr):
for i in range(1, len(arr)):
current_value = arr[i]
j = i - 1
# 尋找合適的位置並移動較大的元素
while j >= 0 and arr[j] > current_value:
arr[j + 1] = arr[j]
j -= 1
# 插入當前值
arr[j + 1] = current_value
# 測試
my_list = [7, 5, 9, 1, 3]
insertion_sort(my_list)
print("排序後的數列：", my_list)python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
# print(arr)
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
arr = [64, 25, 12, 22, 11]
print("未排序數列:", arr)
sorted_arr = insertion_sort(arr)
print("插入排序後的數列:", sorted_arr)特點
時間複雜度：
- 最佳情況：
，當數據已經排好序時。 - 最壞情況：
，當數據完全逆序時。 - 平均情況：
。
- 最佳情況：
空間複雜度：
，因為它是原地排序演算法，不需要額外的空間。 穩定性：插入排序是一種穩定的排序演算法，相同值的元素在排序後相對位置不會改變。
學習資源
- 插入排序法 Insertion Sort IG
- Comparison Sort: Insertion Sort(插入排序法)
- 排序演算法 選擇排序法與插入排序法
- Day23 [演算法]-插入排序法Insertion Sort
Contributors
lucashsu95