插入排序
1.直接插入排序
默认 L(1) 有序，将 L(2) ~ L(n)依次插入到前面已经排好序的子序列中。
空间效率：O(1) ,就地排序
时间效率：比较和移动。最好情况下，有序，只需要比较不需要移动，只要 O(n)。
平均是 O (n2)
稳定性：稳定。
适用性：均可。
2.折半插入排序
主要区别是减少了比较次数，因为比较过程中采用了 折半查找，一个元素折半查找是 O(log2N) ，n 个元素折半查找是 O(n log2n)。
加上移动，所以时间复杂度是 O (n2)。
稳定性：稳定。
适用性：有序，顺序存储。
3.希尔排序
缩小增量排序，是直接插入排序的改进版本。根据布长d 分组，距离为d的记录在同一个组中，组内进行直接插入排序。
空间效率：O(1) ,常数个辅助单元
稳定性：不稳定。
适用性：顺序存储。
希尔排序的时间性能优于直接插入排序的原因：
1）刚开始希尔排序的增量比较大，组数比较多，组内元素比较少，各组内直接插入比较快。
2) 之后增量为1的时候，因为文件已经基本有序，这个时候直接插入排序比较快。