白话Shell排序，一分钟理解

迷南。 2023-02-17 03:53 30阅读 0赞

前面我已经介绍了插入排序，可以知道，插入排序每次只能移动相邻的两个元素，这样效率是非常慢的。今天我介绍另一种排序Shell排序。顾名思义Shell排序是由叫Shell这个人发明的（哈哈），其实本质上Shell排序也是插入排序，只不过在此之前要进行分组。所有又可以理解为分组插入排序(**理解分组插入含义特别重要，这里的分组是指逻辑分组)**。惯例，还是举例说明：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]  
（这里的插入排序是在分完组的基础上排序，也就是在组内进行比较）。由此可见，通过第一轮的分组再排序，那些比较小的数据大致上都换到了前面。这就避免了插入排序由于后面的元素特别小，插入到前面时导致需要大幅度的移动元素（默认从小到大排序）。接下来进行第二轮分组+插入排序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]  
可以看到，此时已经非常接近排列好的数组了。接下来进行最后一次分组排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]  
此时已经完成了排序，可以看到随之一步一步的分组+排序。小的数据都移动到了前面，大的数据都移动到了后面。这样就大大减少了移动次数，提升了性能。接下来给出完整代码

/**
         * Shell排序
         * @param arr 待排序的数组
         */
        private static void shellSort(int[] arr){
        
           //最外层循环控制分组，控制步长
            for (int gap = arr.length / 2;gap > 0;gap /= 2){
        
                //插入排序
                //这里要理解为什么i初始等于gap,i = gap,可以参考插入排序
                for (int i = gap;i < arr.length;i++){
        
                    //存储待插入的元素
                    int temp = arr[i];
                    //i - gap >= 0是防止数组下标越界
                    //temp < arr[i - gap])及表示当前待插入元素的值小于前一个元素(这里的前一个元素隔个步长gap个距离)（已经排好的元素)
                    while (i - gap >= 0 && temp < arr[i - gap]){
        
                        arr[i] = arr[i - gap];
                        i -= gap;
                    }
                    //此时循环结束找到了插入位置
                    //直接插入
                    arr[i] = temp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }

运行结果为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 3]  
到此就完成了Shell排序的全部过程,如果还没有理解，自己动手画画图就能明白了。之后会每天更新一点自己的当天的学习内容与心得，望大佬指教。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200612103246550.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200612105718174.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200612110714284.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200612113026600.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center