【算法】【排序】【插入类】希尔排序 ShellSort

曾经终败给现在 2023-10-10 09:33 44阅读 0赞

#include<stdio.h>
    #include <time.h> 
    #include<stdlib.h>
    
    int main(){
        int a[15];
        //设立随机数 
        srand(time(0));  
        for(int i=0;i<15;i++){
            a[i]=rand()%(30);    //随机数范围0到29之间 
        } 
        //数组a的大小 
        int size=sizeof(a)/4;
        //打印数组信息 
        for(int i=0;i<size;i++){
            printf("%d ",a[i]);
        }
            
        void ShellSort(int a[],int size);
        
        ShellSort(a,size);
        
        return 0;
    } 
    
    void ShellSort(int a[],int size){
        int all=size;     
        int l=size;        //比较距离 ：距离l 
    
        //交换两个地址的值 
        void swap(int* i,int* j);
        
        while(true){
            //比较距离减半 
            //若比较距离为0，退出循环 
            l=l/2;
            if(l==0){
                break;
            }
            //输出比较距离的值 
            printf("\n%d\n",l);
            
            //向右比较 
            for(int i=0;i<all-l;i++){
                //如果遇到小的值x在右边 
                if(a[i]>a[i+l]){
                    //先把当前位置的值和x交换 
                    swap(a+i,a+i+l);
                    //如果 当前位置 在当前比较距离下 曾被比较过 
                    if(i-l>=0){
                        //那么还要从此位置开始向左比较
                        for(int j=i;j-l>=0;j=j-l){
                            //直到x移动到合适的位置： *(dx-l)<*dx<*(dx+l) 
                            if(a[j]<a[j-l]){ 
                                swap(a+j,a+j-l);
                            }else{
                            //由于前面的位置已经排序过了，若遇到比x小的数就表示到达合适位置 
                                goto leftend;
                            }
                        }
                    }
                    leftend:{}
                }
            }
        //打印数组信息 
            for(int i=0;i<size;i++){
                printf("%d ",a[i]);
            }    
        }
    }
    
    
    void swap(int* i,int* j){
        int t=*j;
        *j=*i;
        *i=t;
    }

转载于:https://www.cnblogs.com/LPworld/p/11223348.html