插入排序

1）直接插入排序

//直接插入排序，进行增序排序
void InsertSort(SqlList &L){
    //从第2个元素开始，进行i-1轮插入
    for(int i=2;i<=L.length;i++){
        //如果待插入元素与之前元素比较已经属于有序，无需操作，否则执行操作
        if(L.r[i].key<L.r[i-1].key){
            //复制待插入元素为哨兵
            L.r[0]=L.r[i];
            for(int j=i-1;L.r[0].key<L.r[j].key;j--) //比待插入元素大的都往后移
                    L.r[j+1]=L.r[j];
            L.r[j]=L.r[0];
        } //if
    } //for
} //InsertSort

2）折半插入排序

void BInsertSort(SeqList &L)
{
      //从第二个元素开始把待排序序列插入到有序序列
    for(int i=2;i<=L.length;i++)
    {
        L.r[0]=L.r[i]; 
        int low=1,high=i-1; //从第i-1个元素（有序序列的最后一个元素）开始往前找空
        while(low<=high){ //当low=high,还执行一次，将mid与low，high指向相同位置，并因此会执行else语句，使high+1位置为待插入元素的位置
             mid=(low+high)/2;
             if(L.r[mid].key<L.r[0].key) low=mid+1;
                else high=mid-1;
        } //循环结束，high+1为插入位置
        for(int j=i-1;j>high+1;--j) L.r[j+1]=L.r[j];
        L.r[high+1]=L.r[0];
    }
}

3）希尔排序

//一趟增量为dk的希尔排序
void ShellSort(SeqList &L,int dk){
    for(i=dk+1;i<=L.length;i++){ //从dk+1个元素开始，把无序子序列的元素插入有序序列
        if(L.r[i]<L.r[i-dk]){ //当第i个元素比他前面子序列的元素要小，则执行，否则已经有序，无需操作
            L.r[0]=L.r[i]; //复制为哨兵
            for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);j-=dk) //比L.r[i]大的元素后移空位置
                L.r[j+dk]=L.r[j];
             L.r[j]=L.r[0];
        }
    }
}