插入排序
1． 直接插入排序算法
基本操作：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录增1的有序表。
时间复杂度：O(n^2)
2． 折半插入排序算法
基本操作：由于直接插入排序的基本操作是在一个有序表中进行查找的和插入的，所以这个“查找”操作可以利用“折半查找”来实现，这样可以减少查找的时间复杂度。
时间复杂度：O(n^2)
3． 2-路插入排序算法
虽然书上说它是折半插入排序的改进，但是我感觉其同于折半插入排序……
4． 表插入排序算法
基本操作：和直接插入排序相比，不同之处仅是以修改2n次指针代替了移动记录，排序过程中所需进行的关键字间比较次数相同。
时间复杂度：O(n^2)
5． 希尔排序算法
基本操作：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
希尔排序的一个特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。 希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难题。因此，到目前为止尚未有人求得最好的增量序列。增量序列可以有各种方法，但需要注意：应使增量序列中的值没有除1之外的公因子；并且最后一个增量值必须等于1。