相對于最簡單的選擇排序扇售，插入排序在解決具有某些規(guī)律的亂序數(shù)組排序時會更有優(yōu)勢前塔，但由于插入排序只會交換相鄰的元素，因此元素只能一點一點的從一端移到另一端承冰。
Shell排序簡單的改進了插入排序华弓，交換不相鄰的元素以對數(shù)組的局部進行排序，并最終用插入排序對局部有序的數(shù)組排序困乒。
public class Shell{
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
while(h<N/3) h = 3*N+1;
while(h>=1){
for(int i=h; i<N; i++){
for(int j=i; j>=h && less(a[j],a[j-h]); j-=h){
exch(a,j,j-h);
}
}
h = h/3;
}
}
}
上面的代碼采用的h序列為1/2(3^k-1)寂屏。
希爾排序的思想是使數(shù)組中任意間隔為h的元素都是有序的。這樣的數(shù)組被稱為h有序數(shù)組。如果h很大迁霎，我們就能將元素移動到很遠的地方吱抚，為實現(xiàn)更小的h有序數(shù)組創(chuàng)造方便。
實現(xiàn)希爾排序的一種方法是對于每個h考廉，用插入排序將h個子數(shù)組獨立的排序秘豹。但因為子數(shù)組是獨立的，更簡單的方法是在h子數(shù)組中將每個元素交換到比他大的元素之前去芝此，只需將插入排序的移動元素的距離由1改為h即可憋肖。
