插入排序：插入排序如何工作？與冒泡排序對比

在編程中，排序是最基礎也最常用的操作之一。無論是處理學生成績、商品價格還是日誌數據，排序都能幫我們快速整理信息。今天我們來聊聊兩種簡單的排序算法：插入排序和冒泡排序，看看它們是如何工作的，以及它們之間有什麼區別。

插入排序：逐個“插入”的藝術¶

插入排序的核心思想非常直觀，就像我們整理手中的撲克牌——從左到右逐個處理牌，將每張新牌插入到手中已有牌的正確位置。例如，我們有一副無序的牌 [5, 3, 8, 4, 2]，具體步驟如下：

1. 初始狀態¶

假設手中已經有第一張牌 5（默認是“已排序部分”），剩下的牌 3, 8, 4, 2 需要插入。

2. 插入第二張牌 3¶

• 從第二張牌 3 開始，與已排序部分的最後一張牌 5 比較：3 < 5，所以需要將 5 向後移動一位，騰出位置給 3。
• 插入後，已排序部分變爲 [3, 5]。

3. 插入第三張牌 8¶

• 第三張牌 8 與已排序部分的最後一張牌 5 比較：8 > 5，直接放在末尾。
• 已排序部分變爲 [3, 5, 8]。

4. 插入第四張牌 4¶

• 第四張牌 4 從後往前與已排序部分的元素比較：
• 先與 8 比較：4 < 8，8 後移一位；
• 再與 5 比較：4 < 5，5 後移一位；
• 再與 3 比較：4 > 3，找到正確位置，插入後已排序部分變爲 [3, 4, 5, 8]。

5. 插入第五張牌 2¶

• 第五張牌 2 從後往前與已排序部分的元素比較：
• 與 8 比較：2 < 8，8 後移；
• 與 5 比較：2 < 5，5 後移；
• 與 4 比較：2 < 4，4 後移；
• 與 3 比較：2 < 3，3 後移；
• 已到已排序部分開頭，插入後整個數組變爲 [2, 3, 4, 5, 8]。

算法總結：
插入排序的步驟是從第二個元素開始遍歷，對每個元素 key，從當前位置往前比較，找到正確的插入位置後，將已排序部分的元素後移，最後插入 key。僞代碼如下：

for i from 1 to n-1:  // 從第二個元素開始
    key = arr[i]
    j = i - 1       // 已排序部分的最後一個元素索引
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]  // 元素後移
        j = j - 1
    arr[j+1] = key  // 插入key到正確位置

冒泡排序：相鄰元素的“大冒險”¶

冒泡排序的核心思想是“相鄰元素比較，大的往後冒”。想象水中的氣泡，最大的氣泡會先浮到水面（數組末尾），然後次大的氣泡再浮上來，直到所有氣泡排好序。

冒泡排序示例（以數組 [5, 3, 8, 4, 2] 爲例）¶

• 第一輪：從第一個元素開始，相鄰比較，將大元素“冒泡”到末尾：
• 5 和 3 比較：5 > 3，交換 → [3, 5, 8, 4, 2]；
• 5 和 8 比較：5 < 8，不交換；
• 8 和 4 比較：8 > 4，交換 → [3, 5, 4, 8, 2]；

• 8 和 2 比較：8 > 2，交換 → [3, 5, 4, 2, 8]。
  第一輪結束，最大的 8 已“冒泡”到末尾。

• 第二輪：處理前4個元素（排除最後一個 8）：

• 3 和 5 比較：不交換；
• 5 和 4 比較：5 > 4，交換 → [3, 4, 5, 2, 8]；

• 5 和 2 比較：交換 → [3, 4, 2, 5, 8]。
  第二輪結束，第二大的 5 到了倒數第二位。

• 第三輪：處理前3個元素（排除最後兩個）：

• 3 和 4 比較：不交換；

• 4 和 2 比較：交換 → [3, 2, 4, 5, 8]。
  第三輪結束，第三大的 4 到了倒數第三位。

• 第四輪：處理前2個元素（排除最後三個）：

• 3 和 2 比較：交換 → [2, 3, 4, 5, 8]。
  第四輪結束，整個數組排好序。

算法總結：
冒泡排序需要 n-1 輪（n 爲數組長度），每輪比較相鄰元素，將大元素後移。每輪結束後，未排序部分會少一個元素。

插入排序 vs 冒泡排序：誰更優？¶

總結¶

插入排序和冒泡排序都是簡單的 O(n²) 排序算法，但插入排序在實際應用中更高效，尤其是數據接近有序時。冒泡排序雖然直觀，但移動元素的次數更多（每次比較都可能交換），而插入排序只需在確定位置後移動元素，交換次數更少。

對於初學者來說，理解這兩種排序的核心思想（插入 vs 冒泡）是掌握更復雜排序算法（如快速排序、歸併排序）的基礎。