像整理桌面一樣學插入排序：原理與代碼

一、從整理桌面開始理解插入排序¶

想象一下，你的書桌上堆滿了各種書籍，有的疊在一邊，有的散落在各處，看起來亂糟糟的。現在你想把它們按從左到右（比如從薄到厚、或從A到Z的書名順序）排好。你會怎麼做？

最直觀的思路：先把最左邊的一本書（比如《Python編程》）固定在原位，然後從剩下的書裏隨便拿一本（比如《數據結構》），看看它應該放在哪裏——如果它比《Python編程》厚（假設按厚度排序），就放在《Python編程》右邊；如果薄，就放在左邊。接着再拿下一本書（比如《算法導論》），和已經排好的書比較，找到合適的位置插入……

這個過程是不是很像我們即將要講的插入排序？插入排序的核心思想，就是把“待排序的元素”像整理桌面時的書一樣，逐個插入到“已排序部分”的正確位置，直到所有元素都排好序。

二、插入排序的基本思想¶

插入排序的邏輯可以分爲兩步：
1. 初始化已排序部分：默認數組的第一個元素已經是“排好序的”（因爲單個元素天然有序）。
2. 逐個插入未排序元素：從第二個元素開始（即數組索引1的位置），依次處理後面的每個元素。對於當前元素，將它與前面已排序的元素逐個比較，找到它應該插入的位置，然後將該位置之後的元素後移一位，把當前元素“插入”到正確位置。

三、用例子演示插入排序過程¶

假設我們要對數組 [5, 3, 8, 2, 4] 進行從小到大排序。我們用“整理桌面”的類比來一步步看：

初始狀態：書桌上的書是 [5, 3, 8, 2, 4]（數字代表書的厚度，假設5是最厚的，2是最薄的）。我們需要按厚度從小到大排列。

第一步：第1本書（5）已經在原位，已排序部分是 [5]。
第二步：處理第2本書（3）。此時已排序部分是 [5]，3比5薄，所以應該放在5左邊。把5後移一位，插入3，現在已排序部分變爲 [3, 5]，未排序部分是 [8, 2, 4]。
第三步：處理第3本書（8）。已排序部分是 [3, 5]，8比5厚，所以直接放在已排序部分末尾，已排序部分變爲 [3, 5, 8]，未排序部分是 [2, 4]。
第四步：處理第4本書（2）。已排序部分是 [3, 5, 8]，需要找到2的位置：
8比2厚，後移一位（數組變爲 [3, 5, 8, 8, 4]？不對，這裏需要明確：其實是從後往前比較，把已排序部分的元素後移，給當前元素騰出位置。正確過程是：
- 2和8比較（8>2），8後移一位（數組變爲 [3, 5, 8, 8, 4] ？不，數組是 [3,5,8,2,4]，當前元素是2，i=3（索引從0開始），j從i-1=2開始（即8）。因爲8>2，所以把8後移到i位置（即索引3），數組變爲 [3,5,8,8,4]？不對，此時j=2，i=3，應該是 arr[j+1] = arr[j]，即 arr[3] = arr[2]（把8移到3的位置），j減1到1（5）。
- 5>2，繼續後移：arr[2] = arr[1]（5移到2的位置），j減1到0（3）。
- 3>2，繼續後移：arr[1] = arr[0]（3移到1的位置），j減1到-1（循環結束）。
- 最後插入2到j+1=0的位置，數組變爲 [2, 3, 5, 8, 4]。
第五步：處理第5本書（4）。已排序部分是 [2, 3, 5, 8]，找到4的位置：
8>4，後移：arr[4] = arr[3]（8移到4的位置），j=2（5）。
5>4，後移：arr[3] = arr[2]（5移到3的位置），j=1（3）。
3<4，停止後移，插入4到j+1=2的位置，數組變爲 [2, 3, 4, 5, 8]，排序完成。

四、插入排序的代碼實現（Python）¶

用代碼模擬上面的“整理桌面”過程，核心是：
- 外層循環：遍歷需要插入的元素（從索引1開始）。
- 內層循環：從已排序部分的末尾向前比較，找到插入位置。

def insertion_sort(arr):
    # 外層循環：處理每個待插入的元素（從第二個元素開始）
    for i in range(1, len(arr)):
        current = arr[i]  # 當前要插入的元素
        j = i - 1         # 已排序部分的末尾索引（初始爲i-1）

        # 內層循環：找到插入位置並後移元素
        while j >= 0 and current < arr[j]:
            arr[j + 1] = arr[j]  # 前面的元素比當前大，後移一位
            j -= 1               # 繼續向前比較
        arr[j + 1] = current     # 插入當前元素到正確位置
    return arr

# 測試
arr = [5, 3, 8, 2, 4]
sorted_arr = insertion_sort(arr)
print("排序後：", sorted_arr)  # 輸出：排序後： [2, 3, 4, 5, 8]

五、關鍵點總結¶

核心思想：像整理桌面一樣，將元素逐個插入到已排序部分的正確位置，而非通過交換。
時間複雜度：O(n²)（n爲數組長度），適合小規模數據（比如幾千個元素以內）。
空間複雜度：O(1)（原地排序，不需要額外數組）。
適用場景：數據量小、接近有序的數據（比如已部分排序的數組），或者對內存敏感的場景（空間複雜度低）。

六、和整理桌面的類比呼應¶

已排序部分：相當於書桌上已經按順序排好的區域。
待插入元素：相當於你剛從書堆裏拿出來的新書。
比較與移動：相當於把新書和已排好的書比較，若位置不對就把後面的書“移開”，給新書騰出位置。

通過這種類比，插入排序的邏輯變得像“整理書桌”一樣自然——不需要複雜的交換，只需要耐心地爲每個元素找到正確的“小窩”。

記住：插入排序的本質是“逐個插入”，而非“整體交換”。掌握這個核心，再複雜的排序算法也能從簡單的類比中找到突破口！