CodeGym /課程 /Python SELF TW /插入排序

插入排序

Python SELF TW

等級 58 , 課堂 1

開放

6.1 插入排序的定義

插入排序 (Insertion Sort) 是一種排序演算法，每次將一個元素插入到已排好的數列中。它從未排序的部分取出每個元素，並將其插入到已排序的部分中的正確位置。

工作原理：

從數組的第二個元素開始（第一個元素被認為是已排序的）。
將當前元素與之前的元素比較，並向左移動它，直到找到正確的位置。
對數組的所有元素重複此過程，將每個新元素插入到數組已排序部分的正確位置。

插入排序的時間和空間複雜度

時間複雜度：

最壞情況: O(n^2) — 當元素最初按相反順序排序時發生。
平均情況: O(n^2) — 在元素隨機排列時發生。
最好情況: O(n) — 當元素已經排序時發生。

空間複雜度：

O(1) — 因為算法使用固定數量的額外內存（只有幾個變量用來存儲臨時值）。

6.2 算法的工作分析

在算法的每一步，我們有以下情況：

我們有一個當前索引為i的元素。
所有在它左邊的元素已經從小到大排序。
我們嘗試將我們的當前元素插入數組的已排序部分，以不破壞排序順序。

將元素插入到數組的已排序部分的過程如下：

循環中的變量j從i - 1到0取值。
如果當前 (i-th) 元素小於 j-th 元素，那麼我們將 j-th 元素向右移動一個位置。

例子：當前情況：

綠色代表已經排序的元素。
粉紅色代表尚未排序的元素。
當前元素的索引5用棕色標記。

我們嘗試在數組的已排序部分中找到我們當前元素的正確位置。

步驟 1 — 將當前元素的值記錄到變量 key中。

步驟 2 — 元素 No4 是否大於 key? (10 比 5 大嗎?) 那麼將元素 No4 向右移動：

步驟 3 — 元素 No3 是否大於 key? (8 比 5 大嗎?) 那麼將元素 No3 向右移動：

步驟 4 — 元素 No2 是否大於 key? (6 比 5 大嗎?) 那麼將元素 No2 向右移動：

步驟 5 — 元素 No1 是否大於 key? (4 比 5 大嗎?) 不是。那麼將元素 key 存到元素 No2 原來的位置。

當我們將元素 No5 插入到正確的位置後，我們切換到元素 No6 並嘗試在數組的已排序部分中找到它的位置：

然後取第七個元素：

然後第八個：

6.3 插入排序算法的實現

這是該算法在 Python 中的實現：


def insertion_sort(arr):
    # 遍歷陣列的所有元素，從第二個開始
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1 # 將所有大於key的arr[0..i - 1]元素向右移動一個位置 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1
        arr[j + 1] = key # 將key插入到正確的位置
    return arr  # 返回已排序的陣列
        
# 使用範例：
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("排序後的數組:", sorted_arr)
# 輸出: 排序後的數組: [5, 6, 11, 12, 13]

解釋: