排序(四）希尔排序的两种不同实现

旧城等待， 2022-12-10 15:00 140阅读 0赞

看图  
![4c9155e58850003f7231ab545bc294ed.png][]

广为流传的图 确实很形象

希尔是插入排序的优化

别看他好几个循环 但他的时间复杂度最坏也是跟插入排序一样罢了

思路是这样的

我们需要一个增量gap 他每次都是变化的 每次循环完毕 都会在原来的基础上除2 而默认值为数组长度的一半

他有一个好处 就是在大数据量下 整个排序的次数也不会太大

假如一个数组的长度为10

//第一次循环
    for(int i=5;i<arr.length;i+=5){ 
        for(int j=i-5;j>=0;j-=5){ 
            //每次都是分组 两两比较 交换位置
            if(arr[j]>arr[j+5]){ //证明前一个元素比后一个大
                //交换操作 不写了
            }
        }
    }
    //第二次循环
    for(int i=2;i<arr.length;i+=2){ 
        for(int j=i-2;j>=0;j-=2){ 
            //每次都是分组 两两比较 交换位置
            if(arr[j]>arr[j+2]){ //证明前一个元素比后一个大
                //交换操作 不写了
            }
        }
    }
    //发现了吧 i随增量gap而变化 外层定义个gap循环就可以了
    for(int gap=arr.length/2;gap>0;gap/=2){     
        //每次都减少一倍 ......
    }

完整的代码

//交换法
       for (int gap = arr.length/2; gap >0;gap/=2) { 
                for(int i=gap;i<arr.length;i+=gap){ 
                    for (int j = i-gap; j >=0; j-=gap) { 
                        if(arr[j]>arr[j+gap]){ 
                            arr[j]^=arr[j+gap];
                            arr[j+gap]^=arr[j];
                            arr[j]^=arr[j+gap];
                        }
                    }
                }
            }

移位法 比交换法好许多！！！

这就体现出之前有没有偷懒了 就是插入法移位的思想

外层循环增量是不变的

for(int gap=arr.length/2;gap>0;gap/=2){     
        //......插入内层循环即可
    }
    //内层循环
    for(int i=gap;i<arr.length;i+=gap){ 
        int temp=arr[i];
        int index=i-gap;
        while(index>=0 && arr[index]>temp){ 
            arr[index+gap]=arr[index];
            index-=gap;
        }
    arr[index+gap]=temp;
    }

基础很重要 回到之前说的

移位法要确定两个变量 tmep和index 来使得后面的移位更好操作 否则无从下手

希尔也很好的体现了分治思想 将问题一个个的拆分开来 就变的简单许多了

其实对比之前的插入移位 多了个增量 把原先的±1改成gap也就一样了

总结一下 外层循环的gap是根据数组的长度来变化的 每次都少一倍即可

内层的i随着gap变化 是很跳的 使得循环不是表面看起来的O³ 而是nlogn

再里面移位就是了

有兴趣的可以可以对比下两种方法的差异性

**ps:每一个不曾起舞的日子里 都是对生命的辜负**

[4c9155e58850003f7231ab545bc294ed.png]: /images/20221123/e202fe30a3294ee5b3c36e6c3ab0dd04.png