插入排序

插入排序（Insertion Sort）的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

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

算法原理

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

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

算法分析

• 平均时间复杂度：O(n^2)
• 最差时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 排序方式：In-place
• 稳定性：稳定

如果插入排序的目标是把 n 个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况：

1. 最好情况：序列已经是升序排列，在这种该情况下，需要进行的比较操作需 n - 1 次即可
2. 最坏情况：序列是降序排列，那么此时需要进行的比较共有 n * (n - 1) / 2 次

插入排序的赋值操作是比较操作的次数减去 n - 1 次，平均来说插入排序算法复杂度为 O(n^2)

最优的空间复杂度为开始元素已排序，则空间复杂度为 0

最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(n)

平均的空间复杂度为 O(1)

算法实现

简单插入法

const insertionSort = function (arr) {
  // 数组长度
  const len = arr.length;
  // 当前待插入的值
  let cur;

  // 待排序序列正向遍历（从第二个元素开始遍历，因为第一个元素是第一个被插入的元素）
  for (var i = 1; i < len; i++) {
    cur = arr[i];

    // 有当前扫描的值的索引（排序序列最后一个值的索引）
    let j = i - 1;

    // 有序序列反向遍历，满足两个条件继续扫描：
    // 1. 扫描索引大于 0
    // 2. 当前排序的值小于当前扫描的值
    while (j >= 0 && arr[j] > cur) {
      // 将当前扫描的值向后挪动
      arr[j + 1] = arr[j];
      // 扫描指针向前移动
      j--;
    }

    // 扫描指针到达 0
    // 或当前扫描的值小于当前排序的值
    arr[j + 1] = cur;
  }

  return arr;
};

二分插入法

二分插入排序（Binary Insertion Sort）是对插入排序算法的一种改进。所谓插入排序，就是不断的依次将元素插入前面已排好序的序列中。

二分插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用二分查找法。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依此类推，不断缩小范围，确定要插入的位置。

const binaryInsertionSort = function (arr) {
  for (let i = 1; i < arr.length; i++) {
    let cur = arr[i],
      left = 0,
      right = i - 1;

    // 二分查找
    while (left <= right) {
      // 数组索引中间值
      let mid = Math.floor((left + right) / 2);

      if (cur < arr[mid]) {
        // 查找右半子表
        right = mid - 1;
      } else {
        // 查找左半子表
        left = mid + 1;
      }
    }

    for (let j = i - 1; j >= left; j--) {
      // 统一后移元素，空出插入位置
      arr[j + 1] = arr[j];
    }

    // 插入操作
    arr[left] = cur;
  }

  return arr;
};

二分插入排序仅仅减少了比较元素的次数，约为 O(nLog2 n)，该比较次数与待排序表的初始状态无关，仅取决于表中的元素的个数 n。

而元素的移动次数没有改变，它依赖于待排序表的初始状态，因此二分插入排序的时间复杂度为 O(n^2)。