插入排序

6.1 插入排序的定義

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

工作原理：

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

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

時間複雜度：

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

空間複雜度：

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

6.2 算法的工作分析

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

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

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

1. 循環中的變量j從i - 1到0取值。
2. 如果當前 (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]

解釋:

• 將當前元素儲存在key中
• 將數組排序部分的所有元素向右移動
• 將我們的元素插入到合適的位置

算法工作的例子

我們以數組範例：[12, 11, 13, 5, 6]

1. 第一輪 (i = 1):

• 比較11和12，將12向右移動。
• 數組: [11, 12, 13, 5, 6]

2. 第二輪 (i = 2):

• 13 已經在正確位置。
• 數組: [11, 12, 13, 5, 6]

3. 第三輪 (i = 3):

• 比較5與13, 12 和 11，並將所有向右移動。
• 數組: [5, 11, 12, 13, 6]

4. 第四輪 (i = 4):

• 比較6與13, 12 和 11，並將所有向右移動。
• 數組: [5, 6, 11, 12, 13]

算法完成，因為所有元素都已排序。