12.16 插入排序
待排序对象，插入到前面已排好的地方，边插入边排序，保证子序列都是排好序的。
插入位置
找到这个位置
顺序法：直接插入排序
二分法：二分插入排序
缩小增量多遍插入排序：希尔排序
直接插入排序：
复制插入元素
记录后移，查找插入位置
使用哨兵：
复制为哨兵
记录后移，查找插入位置
（哨兵方法：这里只需要进行一次比较）
插入到正确位置
void InsertSort(SqList &L) {
int i, j;
for (i = 2; i <= L.length; ++i) {
if (L.r[i].key < L.r[i - 1].key) {
L.r[0] = L.r[i];
for (j = i - 1; L.r[0].key < L.r[j].key; --j) {
L.r[j + 1] = L.r[j];
}
L.r[j + 1] = L.r[0];
}
}
} 时复：O（n2）
折半插入排序：
mid = (low + high) / 2
void BinsertSort (SqList &L) {
for (i = 2; i <= L.length; ++i) {
L.r[0] = L.r[i];
low = 1;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (L.r[0].key < L.r[mid].key)
high = mid - 1;
else
low = mid + 1;
}
for(j = i - 1; j >= high + 1; --j)
L.r[j + 1] = L.r[j];
L.r[high + 1] = L.r[0];
}
} 希尔排序：...放一放
