插入排序

1. 直接插入排序

• 查找出L(i)在L[1...i-1]中的插入位置k
• 将L[k...i-1]中所有元素全部后移一个位置
• 将L(i)复制到L(k)

稳定排序，适用于顺序存储和链式存储，时间复杂度为

void InsertSort(ElemType A[], int n){
    int i,j;
    for(i=2; i<=n; i++){
        if(A[i].key<A[i-1].key){
            A[0]=A[i];
            for(j=i-1; A[0].key<A[j].key; --j){
                A[j+1]=A[j];
            }
            A[j+1]=A[0];
        }
    }
}

2. 折半插入排序

稳定排序, 时间复杂度为, 比较次数

void HalfInsertSort(ElemType A[], int n){
    int i, j, low, high, mid;
    for(i=2; i<=n; i++){
        A[0]=A[i];
        low=1;
        high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid].key>A[0].key){
                high=mid-1;
            }
            else{
                low=mid+1;
            }
        }
        for(j=i-1; j>high+1; --j){
            A[j+1]=A[j];
        }
        A[high+1]=A[0]; 
    }
}

3. 希尔排序

不稳定排序，仅适用于线性表为顺序存储的情况

void ShellSort(ElemType A[], int n){
    for(dk=n/2; dk>=1; dk/=2){
        for(i=dk+1; i<=n; ++i){
            if(A[i].key<A[i-dk].key){
                A[0]=A[i];
                for(j=i-dk; j>0&&A[0].key<A[j].key; j-=dk){
                    A[j+dk]=A[j];
                }
                A[j+dk]=A[0]
            }
        }
    }
}