插入排序（Insertion Sort）

认识

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入,类似于我们整理手中的扑克牌 ,一次只处理一个元素，每次都将当前元素插入到已排序部分的正确位置。

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

// 功能测试
const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
insertionSort(arr)
console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

核心思想

将数组分为两个部分：

已排序部分：初始时只包含第一个元素

未排序部分：包含其余所有元素

算法通过从未排序部分取出一个元素，并将其插入到已排序部分的适当位置，从而不断扩大已排序部分，直到整个数组排序完成。

时间复杂度

• 最坏时间复杂度：O(n²) - 当数组是逆序时
• 平均时间复杂度：O(n²)
• 最好时间复杂度：O(n) - 当数组已经有序时

空间复杂度

• O(1) - 只需要常数级别的额外空间

优缺点

优点

1. 实现简单，容易理解
2. 对于小规模数据或基本有序的数据效率较高
3. 是稳定排序算法（相等元素的相对顺序不变）
4. 是原地排序算法，不需要额外空间

缺点

1. 对于大规模数据效率较低
2. 最坏情况下时间复杂度为O(n²)

适用场景

1. 数据规模较小
2. 数据基本有序
3. 需要稳定排序的场景
4. 内存受限的场景