数据结构 -- 插入排序（直接插入排序和希尔排序）

插入排序

算法思想

每次将⼀个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

代码实现

void InsertSort(int A[],int n){
    int i,j,temp;
    for(i = 1;i<n;i++){
        if(A[i]<A[i-1]){
            temp = A[i];			//用temp暂存A[i]
            for(j=i-1;j>=0&&A[j]>temp;--j)		//检查所有前面已经排好序的元素
                A[j+1]=A[j];				//所有大于temp的元素都往后挪一位
            A[j+1]=temp;					//复制到插入位置
        }
    }
}

代码实现（带哨兵）

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

优点：不需要每轮循环都判断一次j>=0

算法效率分析

优化 – 折半插入排序

先用折半查找找到应该插入的位置，再移动元素

当low>high时折半查找停止，并将low之后的元素全部右移，并将A[0]复制到low所在位置

为了保证算法的稳定性，当A[mid]=A[0]时，应继续在mid所指的右边寻找插入位置

void InsertSOrt(int A[],int n){
    iint 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]>A[0]) 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];
    }
}

比起“直接插入排序”，比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度仍未O(n²)

希尔排序

算法思想

先将待排序表分割成若干形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。

……

//希尔排序
void ShellSort(int A[],int n){
    int d,i,j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(i=d/2;d>=1;d=d/2)
        for(i=d+1;i<=n;++i)
            if(A[i]<A[i-d]){
                A[0]=A[i];
                for(j = i-d;j>0&&)
            }
}

目前无法用数学⼿段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)

稳定性：不稳定

适⽤性：仅适⽤于顺序表，不适⽤于链表