js的算法-插入排序（折半插入排序）

直接插入排序的步骤

1. 从前面的有序子表中查找出待插入元素应该被插入的位置

2. 给插入位置腾空间

3. 将待插入元素复制到表中的插入位置。

直接插入排序：边比较边移动；

折半插入排序

先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。

基本思想

1. 将待排序序列的第一个元素看做有个有序序列，把第二个元素到最后一个元素看做未排序序列。

2. 从头（第二个元素）到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置；在查找元素的适当位置时，采用折半查找的方式。也就是说，折半查找的是有序序列中合适的位置。(如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面)。

演示

只展示一个效果，下次再补充后面的循环；

代码展示

let ary = [3, 8, 1, 9, 4, 5, 6, 2, 7];
/**
 *
 * @param {*} ary 数组
 * @param {*} length 长度
 */
function halfSort(ary, length) {
  for (let i = 1; i < length; i++) {
    // 从第二个元素开始扫描
    let temp = ary[i];
    let low = 0,
      high = i - 1; // 标记有序队列
    // 折半查找有序子列
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (ary[mid] > temp) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    // 统一移动位置，从后向前移动，腾出位置
    for (let j = i - 1; j >= high + 1; j--) {
      ary[j + 1] = ary[j];
    }
    ary[high + 1] = temp;
    console.log("ary", JSON.stringify(ary));
  }
}
halfSort(ary, ary.length);

结果：

ary [3,8,1,9,4,5,6,2,7]
ary [1,3,8,9,4,5,6,2,7]
ary [1,3,8,9,4,5,6,2,7]
ary [1,3,4,8,9,5,6,2,7]
ary [1,3,4,5,8,9,6,2,7]
ary [1,3,4,5,6,8,9,2,7]
ary [1,2,3,4,5,6,8,9,7]
ary [1,2,3,4,5,6,7,8,9]

性能分析

总结：

1. 折半插入排序仅仅减少了比较元素的次数，约为O（nlogn）;

2. 比较次数与待排序表的初始状态无关，仅仅取决于表中的元素个数n

3. 元素的移动次数并未改变，它依赖与待排序表的初始状态。

4. 折半插入排序是一种稳定的排序方法

5. 只适用于顺序表，不适用链表