一、直接插入排序

1、直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的元素按其元素值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

2、算法步骤：

(1)、从待排序的第二个元素开始，向下扫描列表，比较这个目标值target与arr[i-1]、arr[i-2]的大小，依次类推。如果target的值小于或等于每一个元素值，那么每个元素都会向右滑动一个位置，一旦确定了正确位置j，目标值target（即原始的arr[i]）就会被复制到这个位置。

3、实例图解：

4、算法分析：

时间复杂度：当元素初始化就是正序排列的，时间复杂度为O(N)，当元素初始化是逆序的，时间复杂度为O(N^2),所以平均时间复杂度为O(N^2)

空间复杂度：在直接插入排序中只使用了i,j,temp这3个辅助元素，与问题规模无关，所以空间复杂度为O(1).

稳定性：在整个排序结束后，即使有相同元素它们的相对位置也没有发生变化，所以直接插入排序是一种稳定排序。

二、折半插入排序

1、折半插入排序的基本思想与直接插入排序一样，在插入第i(i≥1)个元素时，前面i−1个元素已经排好序。区别在于寻找插入位置的方法不同，折半插入排序是采用折半查找法来寻找插入位置的。

2、算法步骤：

（1）计算 0 ~ i-1 的中间点，用 temp临时变量元素与中间值进行比较，如果temp元素大，说明要插入的这个元素应该在中间值和temp对应的i之间，反之，就是在i到中间值的位置，这样很简单的完成了折半；

（2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，从而快速的确定出第 i 个元素要插在什么地方；

（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

3、算法分析：

时间复杂度：折半插入排序适合记录数较多的场景，与直接插入排序相比，折半插入排序在寻找插入位置上面所花的时间大大减少，但是折半插入排序在记录移动次数方面和直接插入排序是一样的，所以其时间复杂度为O(N^2)。其次，折半插入排序的记录比较次数与初始序列无关。因为每趟排序折半寻找插入位置时，折半次数是一定的，折半一次就要比较一次，所以比较次数也是一定的。

空间复杂度：同直接插入排序一样，为O(1)。

稳定性：折半插入排序是一种稳定的排序算法。