## 插入排序

### 算法思想

- 从第一个元素开始，该元素可以认为已经被排序

- 取出下一个元素，在已经排序的元素序列中从后向前扫描

- 如果该元素（已排序）大于新元素，将该元素移到下一位置

- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置

- 将新元素插入到该位置后

- 重复步骤 2 ~ 5

### 代码实现

#### 直接插入排序

```javascript
function insertSort(arr) {
  if (!arr || arr.length <= 2) {
    return;
  }

  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      // 在已排序好的队列中从后向前扫描
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}

let sortArr = [3, 6, 4, 2, 11, 10, 5];

console.log(insertSort(sortArr)); // [ 2, 3, 4, 5, 6, 10, 11 ]
```

**可以这么理解，假设现在已经排序成了 [3, 4, 6, 2, ...]**

```javascript
frist : i = 3， temp = arr[3] = 2， j = 3-1 = 2

while(2 >= 0 && arr[2] > temp) { // (arr[2] = 6) > (temp = 2)
  arr[2+1] = arr[2] // arr[3] = arr[2] = 6，数组顺序为 [3, 4, 6, 6, ...]
  j--
}

j--后等于1,继续while循环
while(1 >= 0 && arr[1] > temp) { // (arr[1] = 4) > (temp = 2)
  arr[1+1] = arr[1] // arr[2] = arr[1] = 4，数组顺序为 [3, 4, 4, 6, ...]
  j--
}

j--后等于0,继续while循环
while(0 >= 0 && arr[0] > temp) { // (arr[0] = 3) > (temp = 2)
  arr[0+1] = arr[0] // arr[1] = arr[0] = 3，数组顺序为 [3, 3, 4, 6, ...]
  j--
}

此时结束while循环，j--后为-1，于是将2插入在a[0]=3的前面
arr[j+1] = temp // j+1 的目的就不用说了吧～
```

这就是插入排序的算法，但是插入排序有`直接插入排序`、`二分插入排序`以及`希尔排序`

我们上边就是最经典的直接插入排序，但直接比较插入排序的交换操作太大，可以采用二分查找法来减少比较操作的数目。也可以称为 `二分插入排序`

#### 二分插入排序

```javascript
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i],
      left = 0,
      right = i - 1;
    // 缩小范围
    while (left <= right) {
      // 利用折半查找插入位置
      let middle = parseInt((left + right) / 2);
      if (arr[middle] > temp) {
        // 插入值小于中点值
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    }
    // left即为找到的要插入的位置，所以下边的循环将left-(i-1)位置的元素依次向后移动
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }
    arr[left] = temp; // 将temp插入到left位置
  }
  return arr;
}
var arr = [3, 6, 4, 2, 11, 10, 5];
console.log(insertSort(arr));
```

### 希尔排序

搞不动了，前端面试搞定前两个就已经 ok 了 🙏

### 时间复杂度和空间复杂度

如果序列是完全有序的，插入排序只要比较 n 次，无需移动，时间复杂度为 O(n)

如果序列是逆序的，插入排序要比较 `O(n^2)`次，移动 `O(n^2)`，时间复杂度为 `O(n^2)`

总得来说，时间复杂度最好的情况是 `O(n)`,最差的情况是 `O(n^2)`， 平均复杂度为 `O(n^2)`