原文链接：

由上图可看到希尔排序先约定一个间隔（图中是4），然后对0、4、8这个三个位置的数据进行插入排序，然后向右移一位对位置1、5、9进行插入排序按照此规律直到全部参与了排序。然后将间隔约定为4-1=3，然后继续进行如上的排序方法。具体过程如下：

9 1 2 3 0 4 5 7 6 8 

Setp 1 经过间隔为4排序后变成 : 0 1 2 3 6 4 5 7 9 8

Setp 2 经过间隔为3排序后变成 : 0 1 2 3 6 4 5 7 9 8

Setp 3 经过间隔为2排序后变成 : 0 1 2 3 5 4 6 7 9 8

Setp 4 经过间隔为1排序后变成 : 0 1 2 3 4 5 6 7 9 8

 

减小间隔：对于大的数组一开始的间隔也应该比较大，而且间隔的缩减幅度也应该变大了，比如对于一个1000大小的数组进行排序可以采用间隔为:364、121、40、13、4、1，这里的间隔序列由knuth提出，数列以逆向的形式从1开始，通过递归表达式h=3*h+1来产生，初始值为1.(其他方法也可以产生序列)如下表

 

下面是希尔排序java代码

public static void shellSort(long[] arr , int eleNum){    int i,j;    long temp;    // 先求出h    int h = 1;    while(h < eleNum / 3)	h = 3 * h + 1; // 1、4    while (h > 0) {	for(i = h ; i < eleNum ; i = i + h) {	    // 对子数组进行排序	    temp = arr[i];	    j = i;	    while(j > h-1 && temp <= arr[j-h]) {	        arr[j] = arr[j-h];		j-=h;	    }	        arr[j] = temp;        }	h = (h-1)/3;    }    System.out.println(Arrays.toString(arr));}