1.直接插入排序

//直接插入排序
void InsertSort(ElemType A[], int n){
    int i,j;
    for(i=2;i<=n;i++)               //依次将A[2]~A[n]插入到前面已排序列
        if(A[i].key<A[i-1].key){    //若A[i]的关键码小于其前驱，将A[i]插入有序表
            A[0]=A[i];              //复制为哨兵，A[0]不存放元素
            for(j=i-1;A[0].key<A[j].key;--j)    //从后向前查找待插入位置
                A[j+1]=A[j];                    //向后挪位
            A[j+1]=A[0];                        //复制到插入位置
        }
}

2.折半插入排序

折半插入排序先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。

//折半插入排序  void InsertSort(ElemType A[], int n) {
    int i,j,low,high,mid;
    for(i=2;i<n;i++){                //依次将A[2]~A[n]插入到前面的已排序序列 
        A[0]=A[i];                //将A[i]暂存到A[0]中 
        low=1;high=i-1;                //设置折半查找范围       
        while(low<=high){            //折半查找 
            mid=(high+low);            //取中间点 
            if(A[mid].key>A[0])   high=mid-1;    //查找左子树 
            else low=mid+1;                //查找右子树 
        } 
        for(j=i_1;j>=high+1;--i)
            A[j=1]=A[j];                //后移元素，空出插入位置 
        A[high+1]=A[0];                    //插入操作 
  
    } }

3.希尔排序

希尔排序的基本思想：先将待排序表分割成若干形如L[i,i+d,i+2d,…i+kd]的特殊子表，分别进行直接插入排序，当整个表中的元素已呈基本有序时，在对全体记录进行一次直接插入排序。

//希尔排序 
void ShellSort(ElemType A[], int n) {
    for(dk=n/2;dk>=1;dk=dk/2)            //步长变化 
        for(i=dk+1;i<=n;++i)      
            if(A[i].key<A[i-dk].key){    //需将A[i]插入有序增量子表 
                A[0]=A[i];                //暂存在A[0]中 
                for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk)
                    A[j+dk]=A[dk];        //记录后移，查找插入位置 
                A[j+dk]=A[0];            //插入操作 
            }
}

希尔排序是不稳定的排序方法，且希尔排序算法仅适用于线性表为顺序存储的情况。