插入排序和它的进化希尔排序

插入排序的思想是，将序列分为两段序列，前面的序列是有序的，后面的是无序的，不断的将无序的序列中的元素往前面那个序列插入。

代码描述：（注意，这里的顺序表都是定义成0号位不用，那些接口adt也是相对应的，比如说初始化你传入的元素个数为6，其实开创的是7个元素的空间。）

//顺序表结构体定义
typedef struct {
    int * elem;//基址空间
    int length;//当前长度
    int size;//储存容量
    int increment;//扩容的增量
}SqList;


//直接插入算法描述：
int InsertSort(SqList & L) {
    if (L.elem == NULL) {
        return ERROR;
    }
    int i,j;

    //可以这么想，就i到哪哪里之前就已经是有序项了，那i指到1，2，3，4倒数第二个3的时候，
    //1，2，3，这三个都是有序的了，而这时要处理的是4，处理完后，i就指到4，也排好了，所以是i<length
    for (i = 1; i < L.length; i++) {
        if (L.elem[i + 1] < L.elem[i]) {//说明要插到前面去，如果比他大就不用插
            L.elem[0] = L.elem[i + 1];//先放到0那存一下
            L.elem[i + 1] = L.elem[i];
            j = i ;//j初始的位置是有序列的最后一个元素
            while (j - 1 != 0 && L.elem[0] < L.elem[j - 1]) {//j所指的是确定已经比i+1大的了
                L.elem[j] = L.elem[j - 1];
                j--;
            }
            L.elem[j] = L.elem[0];
        }
    }
    return OK;
}

希尔排序可以理解为普通插入排序的升级版，就它的思路是先把序列变成基本有序，再进行希尔排序。具体操作是按增量d把序列划分为i个子序列，然后分别对这i个子序列进行插入排序，重复这一过程，直至增量d减到1就对这个基本有序的序列进行一次希尔排序。所以其实思路跟插入差不多。

看代码描述：

int ShellInsert(SqList & L, int dk) {
/*将顺序表按增量dk划分为几个子序列，分别对这几个子序列做插入排序*/
    if (L.elem == NULL) {
        return ERROR;
    }
    int i, j;

    for (i = 1; i <= L.length-dk; i++) {
        if (L.elem[i + dk] < L.elem[i]) {//说明要插到前面去，如果比他大就不用插
            L.elem[0] = L.elem[i + dk];//先放到0那存一下
            j = i + dk;
            do {
                j -= dk;
                L.elem[j + dk] = L.elem[j];//记录后移
            } while (j - dk > 0 && L.elem[0] < L.elem[j - dk]);
            L.elem[j] = L.elem[0];//插入
        }
    }
    return OK;
}

/*对顺序表进行希尔排序*/
int ShellSort(SqList & L, int d[], int t) {
    if (L.elem == NULL)return ERROR;
    int k;
    for (k = 0; k < t; k++) {
        ShellInsert(L, d[k]);//一趟增量为d[k]的增量排序,也就是说第一次的增量为3，第二次为1
    }
    return OK;
}