希尔排序图解(算法原理及代码实例)

希尔排序是Java排序比较重要的一种，本文会以详细介绍希尔排序的基本思想及其代码实现@mikechen

希尔排序定义

希尔排序，英文名为Shell’s Sort，是插入排序的一种，希尔排序，是希尔（Donald Shell）于1959年提出的一种排序算法。

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

 

希尔排序基本思想

希尔排序对插入排序的改进，主要基于以下两点：

1. 插入排序在对几乎已经排好序的数组操作时，效率较高；
2. 整体来看插入排序效率不高，因为每次插入数据只能移动一位数据。

 

希尔排序的基本思路，主要分为如下4步：

1）首先：先将整个待排元素序列切割成若干个子序列分别进行直接插入排序；

2）其次：依次缩减增量再进行排序；

3）最后：待整个序列中的元素基本有序（增量足够小）时，当增量减至1时，整个文件恰被分成一组，算法便终止。

 

希尔排序图解

上面我们理解了大致的思路，下面我们看一个动图就会更加清楚。

下图所示：

排序的详细过程，如下：

 

希尔排序代码案例

上面我们了解了思路与原理，下面我们具体编程程序来实现。

代码如下：

//希尔排序
        public  static void SellSort(int[] arr){
            /*不停对 原数组 进行分组，step为每个数组的元素之间 的距离
            （这里是看作是不同数组，实际在同一个数组中）
              不停的缩小距离（step），则是将数组分得更小，直到step = 1（成为一个数组）
             */
            for(int step = arr.length/2; step > 0 ; step = step/2){
    
                /*
                 从下标step开始为一个数组的第二个数，然后进行插入排序
                 step + 1 为下一个数组第二个数，进行插入排序，以此类推
                 */
                for (int i = step ; i < arr.length; i++){
                    //这操作与插入排序相同，结合插入排序理解
    
                    //记录数以及下标
                    int j = i;
                    int temp = arr[j];
                    //数组的前一个数（arr[j - step]）比trmp大则继续插入，当(j - step) > 0 则说明已经到了数组最前面的数
                    while ((j - step) > 0 && arr[j - step] > temp){
                        arr[j] = arr[j - step];
                        j = j - step;
                    }
                    //找到位置则插入
                    arr[j] = temp;
                }
            }
        }

 

陈睿mikechen

10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》