该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序 然后依次缩减增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。 因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。 　　希尔排序使用序列 h1,h2,.....hn,叫做增量排序，假设hk是代表的步长，对于h1=1时，就是一次插入排序，对于hk躺排序后， 使得每一个i,都满足 a[i] < a[i+hk], (数组中每一个相隔hk元素都有序了)。而对于它的步长一般为 hk = [N/2]和 hk = hk+1/2;     对于希尔排序的最坏的时间复杂度为 O(n3/2) ,其证明的过程是相当复杂的.

java的代码如下:

public static void sort(int[] a){    //步长    for(int gap = a.length/2 ,size=a.length; gap > 0; gap = gap/2){        for(int k=gap; k < size; k++) {            int temp = a[k];            int j= k;            for (; j >= gap && a[j] < a[j - gap]; j = j - gap) {                a[j] = a[j - gap];            }            a[j] = temp;        }    }    Arrays.stream(a).forEach(System.out::println);}