插入排序

核心思想：对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

步骤：

1. 从第二个元素开始，认为第一个元素是已排序部分
2. 取出下一个元素，在已排序部分从后向前扫描
3. 如果已排序部分的元素大于新元素，将已排序部分的元素向右移动一位
4. 重复步骤3，直到找到已排序部分中小于或等于新元素的位置
5. 将新元素插入到该位置
6. 重复以上步骤，直到所有元素排序完成

分析：

• 时间复杂度： 最坏时间复杂度是 O(n^2)，因为最坏情况下需要进行 n(n−1)/2 次比较和移动
• 空间复杂度： 原地排序算法，空间复杂度是 O(1)

实现代码

function insertionSort(arr) {
    let n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    return arr;
}
 
let array = [5, 3, 8, 4, 2];
console.log(insertionSort(array));  // 输出: [2, 3, 4, 5, 8]