# 插入排序



![插入排序](https://firebasestorage.googleapis.com/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdzWW4gUJKke6s2odrw%2Fuploads%2F86sRXkyP28doFlXq1e4x%2Ffile.gif?alt=media)

## 思路

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

## 代码实现

```javascript
function insertionSort(arr){
    let len = arr.length;
    
    for(let i=1;i<len;i++){
        let _pre = i-1,
            curr = arr[i];
        while(_pre>=0 && curr<arr[_pre]){
            arr[_pre+1] = arr[_pre];
            _pre--;
        }
        // 插入
        arr[_pre+1] = curr;
    }
    
    return arr;
}
```

