2020-12-05

插入排序

直接插入排序

//直接插入排序
void insertSort1(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++){//1、n个数，要把n-1个数插入比较
        if(A[i]<A[i-1]){//2、如果后面的数小于前面的数，就需要移动位置
            temp=A[i];//temp临时存放当前要插入的数,i的位置是空出来了的
            for(j=i-1;j>=0 && A[j]>temp;j--){//3、需要把已排序的元素逐步向后挪位，为新元素提供插入空间
                A[j+1]=A[j];
            }
            A[j+1]=temp;//4、插入

        }
    }
}

折半插入排序

//折半插入排序（前面的A[0],A[1]必须是已经排好序的），其实A[0]就是哨兵；分为5步
void insertSort2(int A[],int n){
    int i,j,low,high,mid,temp;
    temp=A[0];  //A[0]必须先保存下来，防止被覆盖
    for(i=2;i<n;i++){  //1、依次将A[2]~A[n-1]插入前面的已排序序列
        A[0]=A[i];  //将A[i]暂时存到A[0]，即是将要插入的数据临时存放在哨兵里面
        low=1;high=i-1; //2、设置折半查找的范围，范围是A[low]~A[high]
        while(low<=high){//3、折半查找（默认递增有序）
            mid=(low+high)/2;   //取中间点
            if(A[mid]>A[0]){
                high=mid-1;//查找左半子表
            }else{
                low=mid+1;
            }
        }
        for(j=i-1;j>=low;j--){//4、统一后移low到i-1的元素，空出插入位置.提示：high+1=low
            A[j+1]=A[j];    //
        }
        A[low]=A[0]; //5、插入操作
    }
    A[0]=temp;
}

希尔排序

//希尔排序
void ShellSort(int A[],int n){
    int d,i,j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(d=n/2;d>=1;d=d/2){//步长变化
        for(i=d+1;i<=n;++i){
            if(A[i]<A[i-d]){//需要将A[i]插入有序增量子表
                A[0]=A[i];//暂存在A[0]
                for(j=i-d;j>0&&A[0]<A[j];j-=d){
                    A[j+d]=A[j];//记录后移，查找插入位置
                }
            A[j+d]=A[0];//插入
        }
        }
    }
}