如何用Python寫插入排序演算法？
插入排序是一種簡單直觀的排序演算法，它的想法是將待排序的陣列分成有序部分和無序部分，每次從無序部分中選擇一個元素插入到有序部分的正確位置。插入排序演算法的實作通常透過多次比較和交換元素來實現，時間複雜度為O(n^2)。
下面我們就來看看用Python語言如何寫插入排序演算法，以及具體的程式碼範例。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # 当前待插入元素
j = i - 1 # 有序部分的最后一个元素索引
# 将比key大的元素都向后移动一位
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 将key插入正确位置
return arr以上是插入排序演算法的具體實作程式碼。在主函數中，我們需要傳入一個待排序的陣列arr，並將排序後的結果傳回。
在演算法的主要循環中，我們從第二個元素開始，將其作為待插入元素key。然後，我們將key與有序部分的最後一個元素進行比較，將比key大的元素向後移動一位，直到找到key的正確位置。最後，我們將key插入到正確位置。
接下來，我們可以測試一下這個插入排序演算法。
arr = [9, 5, 1, 6, 8, 2] sorted_arr = insertion_sort(arr) print(sorted_arr)
輸出結果為：
[1, 2, 5, 6, 8, 9]
可以看到，透過插入排序演算法，我們成功地將輸入的陣列依照升序排列。
總結起來，使用Python編寫插入排序演算法並不複雜。我們只需要理解插入排序的基本思想，然後根據思想實現相應的程式碼。當然，為了讓程式碼更加健壯和通用，我們也可以對邊界情況進行處理，例如空數組或只有一個元素的數組。
希望本文能對您理解並掌握插入排序演算法有所幫助！
以上是如何用Python寫插入排序演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
