# 插入排序（不稳定）

时间复杂度：O(n²)

# 思路

定义两个指针preIndex（已排队列的尾指针）、curValue（当前待排值）。
遍历待排队列，根据preIndex（从后向前）、curValue 与 当前preIndex对应值 大小比较
根据情况不断调整已排队列的尾部的值
最后将curValue放到已排队列的尾部。

const insertSort = arr => {
    let prevIdx,
        curVal,
        len = arr.length;
    
    for (let i = 1; i < len; i++) {
        prevIdx = i - 1;
        curVal = arr[i];

        while (prevIdx >= 0 && curVal < arr[prevIdx]) {
            arr[prevIdx + 1] = arr[prevIdx];
            prevIdx--;
        }

        arr[prevIdx + 1] = curVal; // 注意此处为 prevIdx + 1，因为就算不移动，也是要插入到 prevIdx 的后一位
    }

    return arr;
}

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

# 大致步骤

从无序序列中依次选择一个元素，按它的大小在已排序列中从后向前扫描，插入到相应位置。直到所有的记录都插入为止。

# 具体步骤

例子：[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]，结束排序。