直接插入排序的步骤

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]

性能分析

时间复杂度	空间复杂度
最好的时间复杂度O（nlogn）;最坏时间复杂度O（n^2）	O（1）
平均时间复杂度O（n^2）

总结：

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

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

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

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

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