如何用Python寫插入排序演算法？

如何用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中文網其他相關文章！