# 插入排序（稳定）

时间复杂度：O(n²)

# 思路

不断通过构建 有序序列：对于未排序数据，在已排序序列中 从后向前扫描，找到相应位置并插入。

# 大致步骤

从第一个元素开始（第二元素可以认为已被排序）
取出下一个元素，在已排序序列中从后向前扫描
如果 “已排序的该元素” 大于 “新元素”，将该元素移到下一个位置
重复步骤3，直到找到已排序的元素小于或等于新元素的位置
将新元素插到该位置后，插入完成
继续取下一个元素（重复 2 ~ 5）

const insertSort = list => {
    // prevIdx 表示 已排序序列的尾指针
    let prevIdx;
    // curVal 表示 当前待排元素值
    let curVal;
    
    for (let i = 1; i < list.length; i++) {
        prevIdx = i - 1;
        curVal = list[i];

        while (prevIdx >= 0 && curVal < list[prevIdx]) {
            // 如果 “已排序的该元素” 大于 “新元素”，将该元素移到下一个位置
            list[prevIdx + 1] = list[prevIdx];
            prevIdx--;
        }

        // 直到找到 已排序元素 小于或等于 新元素 的位置，将新元素插到该 “位置后”
        // 注意此处为 prevIdx + 1，因为就算不移动，也是要插入到 prevIdx 的后一位
        list[prevIdx + 1] = curVal;
    }

    return list;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 具体步骤

例子：[1, 9, 7, 6]

一共进行3轮，当前第1轮
有序组是[1]，无序组是[9, 7, 6]（不是真实数组）
取无序组的第一位(9)，赋值temp（9），开始进行排序，此时数组[1, 9, 7, 6]，temp=9
取有序组的最后一位（1）的下标，赋值j，（j=0）
取有序组的最后一位（1），它没有比temp（9）大，不换，此时数组[1, 9, 7, 6]，temp=9，j=0
因为到达有序组顶端（j=0），将temp（9）放到有序组（j+1）位，此时数组[1, 9, 7, 6]，进行第2轮
有序组是[1, 9]，无序组是[7, 6]（不是真实数组）
取无序组的第一位(7)，赋值temp（7），开始进行排序，此时数组[1, 9, 7, 6]，temp=7
取有序组的最后一位（9）的下标，赋值j，（j=1）
有序组最后一位（9）比temp（7）大，将有序组该位置的数覆盖到下一位，此时数组[1, 9, 9, 6]，temp=7，j=1
再往前看是否有更适合的地方，j--，（j=0）
有序组第0位（1），它没有比temp（7）大，不换，此时数组[1, 9, 9, 6]，temp=7，j=0
因为到达有序组顶端（j=0），将temp（7）放到有序组（j+1）位，此时数组[1, 7, 9, 6]，进行第3轮
有序组是[1, 7, 9]，无序组是[6]（不是真实数组）
取无序组的第一位(6)，赋值temp（6），开始进行排序，此时数组[1, 7, 9, 6]，temp=6
取有序组的最后一位（9）的下标，赋值j，（j=2）
有序组最后一位（9）比temp（6）大，将有序组该位置的数覆盖到下一位，此时数组[1, 7, 9, 9]，temp=6，j=2
再往前看是否有更适合的地方，j--，（j=1）
有序组第1位（7）比temp（6）大，将有序组该位置的数覆盖到下一位，此时数组[1, 7, 7, 9]，temp=6，j=1
再往前看是否有更适合的地方，j--，（j=0）
有序组第0位（1），它没有比temp（6）大，不换，此时数组[1, 7, 7, 9]，temp=6，j=0
因为到达有序组顶端（j=0），将temp（6）放到有序组（j+1）位，此时数组[1, 6, 7, 9]，结束排序。