什么是希尔排序？

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

希尔排序原理

1. 选定一个增量h，按照增长量h作为数据分组的依据，对数据进行分组；
2. 对分好组的每一组数据完成 插入排序；
3. 减小增长量，最小减为1，重复第二步操作。

下面是希尔排序算法图示例

关于增长量的确定：

int h=1;
//通过循环来确定分组的最大值
while(h<数组/2){
    h=2h+1;
}
//h的减小规则为每次除以2
h=h/2

希尔排序实现代码

public class Shell {
    public static void sort(Comparable[] a){
        
//        确定h值
        int h = 1;
        while (h<a.length/2){
            h=2*h+1;
        }
        
//        开始希尔排序
//         while循环用于控制每次分组的个数
        while (h>=1) {           
            //首先找到待插入元素
            for(int i=h;i+h<=a.length;i++){        //此处是用于控制分组的移动
                //将待插入元素插入
                for (int j = i;j>=h;j-=h) {        //此处是用于控制需要操作插入的数
                    if(!greater(a[j-h],a[j])){     //待插入数，找到合适的插入位置进行插入
                        exch(a,j,j-h);
                    }
                }
            }
            h=h/2;        //本轮分组排序已经结束，开始减小分组的值，开始新一轮排序
        }
    }


//    两数进行比较的函数，返回true表示a>b，反之a<=b
    private static boolean greater(Comparable a,Comparable b){
        return a.compareTo(b)>0;
    }
    
//    对数组中的两个元素进行交换
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}