希尔排序

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

原理

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

增长量H确定公式 最大

int h = 1;
while( h < (数组的长度 / 2)) {
    h = 2 * h + 1;
}
    

最小

h = h/2;

案例，排序

public class Shell {

    /**
     * 对数组a中的元素进行排序
     */
    public static void sort(Comparable[] a){
        int h = 1;
        while (h < (a.length / 2)) {
            h = 2 * h + 1;
        }

        while (h >= 1) {
            //找到待插入元素
            for (int i = h; i < a.length; i++) {
                //把待插入元素插入到有序数列中
                for (int j = i; j >= h; j -= h) {
                    if (greater(a[j - h], a[j])) {
                        exch(a, j - h, j);
                    } else {
                        break;
                    }
                }
            }
            h = h / 2;
        }
    }

    /**
     *  比较v元素是否大于w元素
     */
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w) > 0;
    }

    /**
     * 数组元素i和j交换位置
     */
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

测试

public class Client {
    public static void main(String[] args) {
        Integer[] a = {4, 5, 6, 3, 2, 1};
        Shell.sort(a);
        System.out.println(Arrays.toString(a));
    }

}

理解图