引言

大家好！歡迎繼續關注我的排序算法系列。今天，我們要學習的是另一種非常基礎且重要的排序算法——插入排序 (Insertion Sort)。

插入排序的思路非常貼近我們日常整理撲克牌的方式，理解起來相對自然。雖然它在最壞情況下的效率不高，但在某些特定場景下，它的表現甚至優于一些更高級的排序算法。

---

什么是插入排序？

想象一下你在玩撲克牌，手里已經握著幾張排好序的牌（比如按點數從小到大）。現在你從牌堆里摸了一張新牌，你會怎么做？

通常，你會從右手邊（或左手邊）已排序的牌開始，逐張比較新牌和手里的牌，找到新牌應該插入的位置，然后將該位置及其后面的牌向后挪動一點，騰出空位，把新牌插進去。

插入排序就是基于這個思想：

1. 將整個數組分為兩部分： 左邊是“已排序”區間，右邊是“未排序”區間。
2. 初始狀態： 已排序區間只包含數組的第一個元素 arr[0]。
3. 逐步擴展： 從未排序區間（從 arr[1] 開始）依次取出元素。
4. 尋找位置并插入： 將取出的元素（我們稱之為 current 或 now）與已排序區間的元素從右向左逐一比較。
5. 移動元素： 如果已排序區間的元素大于 current，則將該元素向右移動一位。
6. 重復比較和移動： 繼續向左比較和移動，直到找到一個小于或等于 current 的元素，或者到達已排序區間的開頭。
7. 插入： 將 current 插入到最后移動元素的那個位置的后面（也就是空出來的位置）。
8. 重復： 對未排序區間的所有元素重復步驟 3-7，直到所有元素都被插入到已排序區間中。

---

算法步驟詳解 (以升序為例)

假設我們有數組 [5, 2, 4, 6, 1, 3]

1. 初始： [5] | [2, 4, 6, 1, 3] ( | 分隔已排序和未排序)
2. 處理 2 (now = 2)：
   • 比較 2 和 5 -> 2 < 5 -> 移動 5 -> [_, 5] | [4, 6, 1, 3]
   • j 變為 -1，循環結束。
   • 插入 2 到 j+1 (即 0) -> [2, 5] | [4, 6, 1, 3]
3. 處理 4 (now = 4)：
   • 比較 4 和 5 -> 4 < 5 -> 移動 5 -> [2, _, 5] | [6, 1, 3]
   • 比較 4 和 2 -> 4 >= 2 -> break 循環 (j 為 0)。
   • 插入 4 到 j+1 (即 1) -> [2, 4, 5] | [6, 1, 3]
4. 處理 6 (now = 6)：
   • 比較 6 和 5 -> 6 >= 5 -> break 循環 (j 為 2)。
   • 插入 6 到 j+1 (即 3) -> [2, 4, 5, 6] | [1, 3]
5. 處理 1 (now = 1)：
   • 比較 1 和 6 -> 1 < 6 -> 移動 6 -> [2, 4, 5, _, 6] | [3]
   • 比較 1 和 5 -> 1 < 5 -> 移動 5 -> [2, 4, _, 5, 6] | [3]
   • 比較 1 和 4 -> 1 < 4 -> 移動 4 -> [2, _, 4, 5, 6] | [3]
   • 比較 1 和 2 -> 1 < 2 -> 移動 2 -> [_, 2, 4, 5, 6] | [3]
   • j 變為 -1，循環結束。
   • 插入 1 到 j+1 (即 0) -> [1, 2, 4, 5, 6] | [3]
6. 處理 3 (now = 3)：
   • 比較 3 和 6 -> 3 < 6 -> 移動 6 -> [1, 2, 4, 5, _, 6]
   • 比較 3 和 5 -> 3 < 5 -> 移動 5 -> [1, 2, 4, _, 5, 6]
   • 比較 3 和 4