# 插入排序

就想着自己在打扑克牌，接起来一张，放哪里无所谓，再接起来一张，比第一张小，放左边，继续接，可能是中间数，就插在中间....依次

{% hint style="info" %}
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

外循环好像起牌，不算拿的第一张，从第二张到最后一张

内循环来比较，对于外循环的牌，逐一逆序两两比较，小的就往前插入，主要遇到大牌就停止
{% endhint %}

* 首先将待排序的第一个记录作为一个有序段
* 从第二个开始，到最后一个，依次和前面的有序段进行比较，确定插入位置

```javascript
function insertSort(arr) {
    for(let i = 1; i < arr.length; i++) {  //外循环从1开始，默认arr[0]是有序段
        for(let j = i; j > 0; j--) {  //j = i,将arr[j]依次插入有序段中
            if(arr[j] < arr[j-1]) {
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
            } else {
                break;
            }
        }
    }
    return arr;
}
```

分析： 注意这里两次循环中，`i`和`j`的含义：

1. `i`是外循环，依次把后面的数插入前面的有序序列中，默认`arr[0]`为有序的，`i`就从1开始
2. `j`进来后，依次与前面队列的数进行比较，因为前面的序列是有序的，因此只需要循环比较、交换即可
3. 注意这里的`break`，因为前面是都是有序的序列，所以如果当前要插入的值`arr[j]`大于或等于`arr[j-1]`，则无需继续比较，直接下一次循环就可以了。