待排序对象，插入到前面已排好的地方，边插入边排序，保证子序列都是排好序的。

        插入位置
        找到这个位置

顺序法：直接插入排序
二分法：二分插入排序
缩小增量多遍插入排序：希尔排序

直接插入排序：
        复制插入元素
        记录后移，查找插入位置
使用哨兵：
        复制为哨兵
        记录后移，查找插入位置
        （哨兵方法：这里只需要进行一次比较）
        插入到正确位置

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];
    }
}

希尔排序：...放一放