插入排序

将数组分为已排序和未排序两部分，每次从未排序部分取一个元素插入到已排序部分的正确位置。

思路

• 第一个元素默认为已排序
• 从第二个元素开始，依次向前遍历已排序部分
• 如果当前元素小于已排序部分的元素，将已排序元素后移
• 找到合适位置后插入当前元素
• 重复直到所有元素排序完成

代码

// 插入排序
// 第一个为有序，后面一个个向前遍历对比

function insertionSort(arr) {
    let j
    for(let i = 1; i < arr.length; i++) {
        let num = arr[i];
        for(j = i - 1; j >= 0; j--) {
            if(num > arr[j]) break;
            else arr[j + 1] = arr[j];
        }
        arr[j + 1] = num;
    }
}

复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定