希尔排序ShellSort

素颜马尾好姑娘i 2022-05-22 00:27 141阅读 0赞

首先来说下百度百科上对希尔排序算法思想的定义:  
该方法实质上是一种分组插入方法  
比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，  
则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。  
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，  
然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。  
引用地址:[https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin][https_baike.baidu.com_item_E5_B8_8C_E5_B0_94_E6_8E_92_E5_BA_8F_3229428_fr_aladdin]  
也就是说希尔排序的实质是:就是将整个数组拆分成小分组然后进行插入排序.  
那么在借用百科上一张图进行解释:  
![这里写图片描述][70]  
第一次分组,分组间隔为5.  
一次分组分为五组,数组下标(0,5),(1,6),(2,7),(3,8),(4,9)的分别为一组,一共五组,然后比较.  
第二次分组,分组间隔为3.  
二次分组分为三组,数组下标(0,3,6,9),(1,4,7),(2,5,8),的分别为一组,一共三组,然后比较.  
第三次分组,分组间隔为1.  
即为整个数组进行插入排序比较.  
由这个思想可以得到下面java实现的代码:

int[] tempArray = new int[]{
       49,38,65,97,76,13,27,49,55,04};
            System.out.println("生成的为排序前的数组为:"+ Arrays.toString(tempArray));
            //每次循环,削减步长
    for (int  increment=tempArray.length / 2; increment > 0; increment /=2) {
                //为了实现跟图片同样的输出效果,定步长为:5,2,1.
                if (increment == 2){
                    increment = 3;
                }
                for (int i = 0; i <tempArray.length-increment; i++) {
                    for (int j = i+increment;j<tempArray.length;j+=increment){
                        if (tempArray[i] > tempArray[j]) {
                            int tempNum = tempArray[i];
                            tempArray[i] = tempArray[j];
                            tempArray[j] = tempNum;
                        }
                    }
                }
                System.out.println("此次排序后的数组为:"+Arrays.toString(tempArray)+"此时的步长为:"+increment);
            }

输出效果如下图所示,与上图显示排序结果步骤及结果一致:  
![这里写图片描述][70 1]  
本节代码博主已经上传到GitHub上,有需要的可以查看,地址:  
[https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/ShellSort.java][https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_ShellSort.java]  
Over!

[https_baike.baidu.com_item_E5_B8_8C_E5_B0_94_E6_8E_92_E5_BA_8F_3229428_fr_aladdin]: https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin
[70]: /images/20220522/414001fe67b842aea28b005babb270b8.png
[70 1]: /images/20220522/d57f93288fe44c149ebe67de6ac47446.png
[https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_ShellSort.java]: https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/ShellSort.java