插入排序的设计初衷是往有序的数组中快速插入一个新的元素. 它的算法思想是: 把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的.

插入排序由于操作不尽相同, 可分为 直接插入排序 , 折半插入排序(又称二分插入排序), 链表插入排序 , 希尔排序 .

直接插入排序

概念：将待排序的元素按照大小顺序, 依次插入到一个已经排好序的数组之中, 直到所有的元素都插入进去.

稳定性

由于直接插入排序每次只移动一个元素的位置, 并不会改变值相同的元素之间的排序, 因此它是一种稳定排序.

演示图

代码实现

function directInsertionSort(array) {
  for (var i = 1; i < array.length; i++) {
    var j = i;
    while (j > 0 && array[j] < arr[j - 1]) {
      swap(j, j - 1, array);
      j--;
    }
  }
  return array;
}

折半插入排序

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

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

步骤

1. 取 0 ~ i-1 的中间点( m = (i-1)>>1 ), array[i] 与 array[m] 进行比较, 若 array[i] < array[m] , 则说明待插入的元素 array[i] 应该处于数组的 0 ~ m 索引之间; 反之, 则说明它应该处于数组的 m ~ i-1 索引之间.

2. 重复步骤 1, 每次缩小一半的查找范围, 直至找到插入的位置.

3. 将数组中插入位置之后的元素全部后移一位.

4. 在指定位置插入第 i 个元素.

注: x>>1 是位运算中的右移运算, 表示右移一位, 等同于 x 除以 2 再取整, 即 x>>1 == Math.floor(x/2) .

function binaryInsertionSort(array) {
  var current, i, j, low, high, m;
  for (i = 1; i < array.length; i++) {
    low = 0;
    high = i - 1;
    current = array[i];

    while (low <= high) {
      //步骤1&2:折半查找
      m = (low + high) >> 1;
      if (array[i] >= array[m]) {
        //值相同时, 切换到高半区，保证稳定性
        low = m + 1; //插入点在高半区
      } else {
        high = m - 1; //插入点在低半区
      }
    }
    for (j = i; j > low; j--) {
      //步骤3:插入位置之后的元素全部后移一位
      array[j] = array[j - 1];
    }
    array[low] = current; //步骤4:插入该元素
  }
  return array;
}

虽然折半插入排序明显减少了查询的次数, 但是数组元素移动的次数却没有改变. 它们的时间复杂度都是 O(n²).