插入排序法 (Insertion Sort) 視覺化教學

1. 操作原理

插入排序法的工作原理是將序列分為「已排序」和「未排序」兩部分。每一輪從未排序部分取出一個元素，將其插入到已排序部分的適當位置，就像整理手中的撲克牌一樣。

第 1 步：從第二個元素開始（假設第一個元素已排序）。
第 2 步：取出該元素，與左側已排序的元素逐一比較。
第 3 步：若左側元素較大，則將其右移，為插入元素騰出空間。
第 4 步：找到正確位置後，將元素插入。

                重點：插入排序是一種穩定、原地排序的方法。
                
核心流程為：取出元素、比較移動、插入位置，適合處理部分有序的資料。

2. 時間及空間複雜度

情況	時間複雜度	空間複雜度	說明	難易度
最佳	O(n)	O(1)	當陣列已經排序時，只需 n-1 次比較，無需移動元素。	簡單
平均	O(n²)	O(1)	隨機資料需要多次比較和移動，平均比較次數約為 n²/4。	中等
最壞	O(n²)	O(1)	陣列完全反序時，每個元素都需要與前面所有元素比較並移動。	困難
空間	—	O(1)	原地排序，只需要一個額外空間來暫存當前處理的元素。	低
穩定性	穩定		相同元素的相對順序不會改變，適合需要穩定排序的場景。	低

3. 互動視覺化

自定義陣列 (逗號分隔)：

動畫速度（右快左慢）：中等

步驟數

比較次數

移動次數

準備就緒 - 請載入或產生陣列

未排序

比較中

當前元素

已排序

📝 步驟紀錄

4. 偽代碼及實作範例

// 偽代碼
for i := 1 to n - 1
    key := A[i]
    j := i - 1
    while j >= 0 and A[j] > key
        A[j + 1] := A[j]
        j := j - 1
    A[j + 1] := key

// JavaScript 範例
function insertionSort(arr) {
    const n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;

        // 將大於 key 的元素向右移動
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        // 將 key 插入正確位置
        arr[j + 1] = key;
    }
    return arr;
}