基本思路：
希爾排序算法是按其設計者希爾（Donald Shell）的名字命名蔚叨，該算法由1959年公布坡脐，是插入排序的一種更高效的改進版本堡牡。它的作法不是每次一個元素挨一個元素的比較怠噪。而是初期選用大跨步（增量較大）間隔比較癌佩，使記錄跳躍式接近它的排序位置嗜憔；然后增量縮型豪；最后增量為 1 吉捶，這樣記錄移動次數(shù)大大減少夺鲜，提高了排序效率皆尔。希爾排序對增量序列的選擇沒有嚴格規(guī)定。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
插入排序在對幾乎已經排好序的數(shù)據(jù)操作時币励， 效率高慷蠕， 即可以達到線性排序的效率
但插入排序一般來說是低效的， 因為插入排序每次只能將數(shù)據(jù)移動一位
步驟：
∈成搿（1） 先取一個正整數(shù) d1(d1 < n)流炕，把全部記錄分成 d1 個組，所有距離為 d1 的倍數(shù)的記錄看成一組仅胞，然后在各組內進行插入排序每辟；
（2）然后取 d2(d2 < d1)干旧；
∏邸（3）重復上述分組和排序操作；直到取 di = 1(i >= 1) 位置椎眯，即所有記錄成為一個組挠将，最后對這個組進行插入排序。一般選 d1 約為 n/2编整，d2 為 d1 /2舔稀， d3 為 d2/2 ，…闹击， di = 1镶蹋。
實例分析
假設有數(shù)組 array = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d1 = 4赏半，將數(shù)組分為 4 組贺归，如下圖中相同顏色代表一組：
然后分別對 4 個小組進行插入排序，排序后的結果為：
然后断箫，取 d2 = 2拂酣，將原數(shù)組分為 2 小組，如下圖：
然后分別對 2 個小組進行插入排序仲义，排序后的結果為：
最后婶熬，取 d3 = 1，進行插入排序后得到最終結果：
代碼實現(xiàn)
public class Shellsort {
public static void main(String[] args){
int[] a= {1,2,5,3,1,667,222,3};
sort(a);
System.out.println(Arrays.toString(a));
}
public static void sort(int[] a){
int gap=1, i, j, len=a.length;
int temp;
while(gap<len/3){
gap = gap*3+1;
}
for(;gap >0; gap/=3){
for(i=gap; i<len; i++){
temp = a[i];
for(j=i-gap;j>=0&&a[j]>temp;j-=gap)
a[j+gap] = a[j]; //交換位置
a[j+gap] = temp; //交換位置
}
}
}
}
