插入排序.md

插入排序

算法思想

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

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

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

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

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

• 重复步骤 2 ~ 5

代码实现

直接插入排序

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, ...]

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 的目的就不用说了吧～

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

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

二分插入排序

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)