---
tags: DSA in JavaScript
---
# Ch. 13 Insertion Sort
- 使用一個指標，將陣列分為 `已排序`(前半部)與 `未排序`(後半部)兩部分
- 指標一開始指向第二個位置，而第一個位置代表 `已排序` ，長度為 1 的陣列可以表示為已排序
- 將指標的元素插入至 `已排序` 的部分
- 完成後，指標改指向 `未排序` 的第一個元素

function insertionSort (arr) {
    // 1. 使用 i 作為可移動的基準點
    for (let i = 1; i < arr.length; i++) {
    // 2. 將 arr[i] 先用 curr 保存下來，因為 arr[i] 之後會被改變
        const curr = arr[i]
    // 3. 在這邊宣告 j 是因為 for 迴圈外面也會用到 j 這個變數
        let j = i - 1
        // 4. 尋找 curr 在已排序部分的位置
        for (; j >= 0 && arr[j] > curr; j--) {
        // 5. 在已排序部分，比 curr 大的數就會往前移一格
            arr[j+1] = arr[j]
        }
        // 6. 最後將 curr 放到適當的位置上
        arr[j+1] = curr
    }
    return arr
}

插入排序的時間複雜度也是 O(n^2^)，不過與前面兩個排序不同，分為左右兩部分的特性，因此適合有即時資料從最後面加進來的情況