希尔排序和插入排序很相似，有点像插入排序的升级版本。

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

希尔排序也是一种插入排序算法，只不过在插入排序上突破了结界，达到了另一种顶峰的存在，这种顶峰使得时间复杂度变成「O(nLogn)~O(n^2)」。

希尔排序是通过分组+插入。

排序步骤:

这里有8个数据,分成4组,每两个进行比较,

比较完毕之后进行缩小增量操作,4/2 =2所以,数据又被分成两组

然后对上面的两组再分别进行直接插入排序,这样整个数组就更有序写,最后再缩小增量2/2=1,这样整个数组就为1组,直接进行简单的插入排序

最后数组就有序了。

实现代码：

public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
        //希尔的第一轮排序
        //因为希尔是第一轮排序,所以分成5组
        for (int i = 5; i <arr.length; i++) {
            //遍历各组中的所有的元素(共有五组,每一组有两个元素,所以步长是5)
            for (int j =i-5 ; j >=0 ; j-=5) {
                //如果当前的元素大于加上步长后的那个元素,说明需要交换
                if (arr[j]>arr[j+5]){
                    int temp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = temp;
                }
            }
        }
        System.out.println("希尔排序一轮后:");
        for(int i=0;i<arr.length;i++) {
        System.out.print(arr[i]+" ");
        }
        System.out.println();
        //希尔的第二轮排序
        for (int i = 2; i <arr.length; i++) {
            for (int j =i-2 ; j >=0 ; j-=2) {
                //如果当前的元素大于加上步长后的那个元素,说明需要交换
                if (arr[j]>arr[j+2]){
                int temp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = temp;
                }
            }
        }
        System.out.println("希尔排序二轮后:");
        for(int i=0;i<arr.length;i++) {
        System.out.print(arr[i]+" ");
        }
        System.out.println();
        //希尔的第二轮排序
        for (int i = 1; i <arr.length; i++) {
            for (int j =i-1 ; j >=0 ; j-=1) {
                //如果当前的元素大于加上步长后的那个元素,说明需要交换
                if (arr[j]>arr[j+1]){
                int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println("希尔排序三轮后:");
        for(int i=0;i<arr.length;i++) {
        System.out.print(arr[i]+" ");
        }
        System.out.println();
}

运行结果：

以上就是推导过程,逐步分析可以知道：

public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
        int count = 0;
        for (int gap = arr.length/2; gap > 0; gap=gap/2) {
            for (int i = gap; i <arr.length; i++) {
                //遍历各组中的所有的元素(共有gap组,每一组有两个元素,所以步长是gap)
                for (int j =i-gap ; j >=0; j-=gap) {
                    //如果当前的元素大于加上步长后的那个元素,说明需要交换
                    if (arr[j]>arr[j+gap]){
                        int temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
            System.out.println("希尔排序第"+(++count)+"轮后:");
            for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+" ");
            }
            System.out.println();
        }
}

运行结果：

这里用的是交换法，效率不是特别高(可以在运行前和运行后统计一下时间)，下面我们用移动法优化一下：

public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
for (int gep = arr.length/2; gep > 0; gep=gep/2) {
         //从第gep和元素,逐个对其所在的组进行直接插入排序
         for (int i = gep; i <arr.length ; i++) {
             int j = i;//保存待插入的下标
             int temp = arr[j];//保存待插入的值
             if (arr[j]<arr[j-gep]){
                 while(j-gep>=0&&temp<arr[j-gep]){//如果说下标减去步长还是大于0的,并且待插入的数还是小于这个前一个步长的数,执行以下操作
                     //移动
                     arr[j] = arr[j-gep];//上述条件,满足后,就开始进行赋值,也就是移动操作
                     j-=gep;//然后gep步长--
                 }
                 //当退出while循环后,就给temp找到了位置
                 arr[j] = temp;
             }
         }
}
System.out.println("希尔排序后：");
for(int i=0;i<arr.length;i++) {
        System.out.print(arr[i]+" ");
     }
}

运行结果：