插入排序又为分为 直接插入排序 和优化后的 拆半插入排序 与 希尔排序，我们通常说的插入排序是指直接插入排序。

一、直接插入

动画

插入排序 - 图1

实现

思想
一般人打扑克牌，整理牌的时候，都是按牌的大小（从小到大或者从大到小）整理牌的，那每摸一张新牌，就扫描自己的牌，把新牌插入到相应的位置。

插入排序的工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤 2~5。

升序的步骤：

  1. 从第 i 个数往前比，比它大的就往后排。
    1. 也就是把第 i 个数，前面比 i 小的第一个数的索引找出来，将第 i 个数塞到它后面
  2. 依次类推，进行到最后一个数
  1. const array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 46, 4, 19, 50, 48];
  3. const insertSort = (arr) => {
  4.   // 从数组第二项开始往前比。
  5.   for (let i = 1, len = arr.length; i < len; i++) {
  6.     const current = arr[i]; // 暂存第 i 项的值
  7.     let preIndex = i - 1; // 待比较元素的下标，用于找出比 arr[i] 小的第一个数的索引
  9.     // 如果前一项比后一项小，可以直接退出，进行下一项的比较
  10.     while (preIndex >= 0 && arr[preIndex] > current) {
  11.       // 走到这里，说明前一项比后一项大，前一项往后排
  12.       arr[preIndex + 1] = arr[preIndex];
  13.       preIndex--;
  14.     }
  15.     arr[preIndex + 1] = current
  16.   }
  17. }
  19. insertSort(array)
  21. console.log(array); // [3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

分析

  • 第一，插入排序是原地排序算法吗 ？
    插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，所以，这是一个原地排序算法。
  • 第二，插入排序是稳定的排序算法吗 ？
    在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
  • 第三，插入排序的时间复杂度是多少 ？
    最佳情况：T(n) = O(n)，当数据已经是正序时。
    最差情况：T(n) = O(n^2)，当数据是反序时。
    平均情况：T(n) = O(n^2)。

二、拆半插入

插入排序也有一种优化算法，叫做拆半插入。

实现

思想
折半插入排序是直接插入排序的升级版，鉴于插入排序第一部分为已排好序的数组，我们不必按顺序依次寻找插入点，只需比较它们的中间值与待插入元素的大小即可。

本质就是利用二分法，在已排序好的数组中，找到比新元素小的第一个值的索引，也就找到插入位置

步骤

  1. 取 0 ~ i-1 的中间点 (m = (i-1) >> 1 )，array[i] 与 array[m] 进行比较
    1. 若 array[i] < array[m]，则说明待插入的元素array[i] 应该处于数组的 0 ~ m 索引之间
    2. 反之，则说明它应该处于数组的 m ~ i-1 索引之间。
  2. 重复步骤 1，每次缩小一半的查找范围，直至找到插入的位置。
  3. 将数组中插入位置之后的元素全部后移一位。
  4. 在指定位置插入第 i 个元素。
  1. const array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 46, 4, 19, 50, 48];
  3. const binaryInsertSort = (arr) => {
  4.   // 从数组第二项开始往前比。
  5.   for (let i = 1, len = arr.length; i < len; i++) {
  6.     const current = arr[i]; // 暂存第 i 项的值
  7.     let high = i - 1;
  8.     let low = 0;
  9.     let mid;
  10.     // 进行二分，找出比第 i 项小的索引
  11.     while (low <= high) {
  12.       mid = (low + high) >> 1; // 可换成 Math.floor((low + high) / 2)，二者精度不同
  13.       if (arr[mid] <= arr[i]) {
  14.         // 值相同时, 切换到高半区，保证稳定性。因为后续会进行遍历赋值，把比第 i 项大的数，往后移一位
  15.         low = mid + 1;
  16.       } else {
  17.         high = mid - 1;
  18.       }
  19.     }
  20.     // 把比第 i 项大的数，往后移一位
  21.     for (let j = i; j > low; j--) {
  22.       arr[j] = arr[j - 1]
  23.     }
  24.     // low 就是第 i 项该插入的位置
  25.     arr[low] = current
  26.   }
  27. }
  29. binaryInsertSort(array)
  31. console.log(array); // [3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

注意：和直接插入排序类似，折半插入排序每次交换的是相邻的且值为不同的元素，它并不会改变值相同的元素之间的顺序，因此它是稳定的。