希爾排序（Shell Sort）是插入排序的一種，也是直接插入排序的更有效率的改進版本，希爾排序充分利用了插入排序的兩個特點：
1）當資料規模小的時候非常有效率。
2）當給定資料已經有序時的時間複雜度為O(n)。
所以，Shell排序每次把資料分成若干塊，來使用插入排序，而且之後在這若干個小塊排好序的情況下把它們合成大一點的小塊，繼續使用插入排序，不停地合併小塊，直到最後一個小塊。
這裡每次分成若干個小小塊是透過「增量」來控制的，開始的時候增量較大，接近n/2，從而使得分割出來接近n/2個小塊，逐漸的減小「增量”，最終減小到1。
例如：
publicclassMain{publicstaticintcount=0;publicstaticvoidshellSort(int[]data){//計算最大的h值inth=1;while(h<=data.length/3){h=h*3+1;}while(h >0){for(inti=h;i<data.length;i+=h){if(data[i]<data[ih]){inttmp=data[i];intj=ih;while(j>= 0&&data[j]>tmp){data[j+h]=data[j];j-=h;}data[j+h]=tmp;print(data);}}//計算出下一個h值h=(h-1)/3;}}publicstaticvoidprint(int[]data){for(inti=0;i<data.length;i++){System.out.print(data[i]+t); }System.out.println();}publicstaticvoidmain(String[]args){int[]data=newint[]{4,6,1,9,5,8};print(data);shellSort(data); print(data);}}運行結果如下：
461958146958145698145689145689