希爾排序(Shell Sort)是插入排序的一種，它是針對直接插入排序算法的改進。
希爾排序又稱縮小增量排序，因 DL.Shell 于 1959 年提出而得名。
它通過比較相距一定間隔的元素來進行，各趟比較所用的距離随着算法的進行而減小，直到隻比較相鄰元素的最後一趟排序為止。
希爾排序時間複雜度是 O(n^(1.3-2))，空間複雜度為常數階 O(1)。希爾排序沒有時間複雜度為 O(n(logn)) 的快速排序算法快 ，是以對中等大小規模表現良好，但對規模非常大的資料排序不是最優選擇，總之比一般 O(n^2 ) 複雜度的算法快得多。
希爾排序目的為了加快速度改進了插入排序，交換不相鄰的元素對數組的局部進行排序，并最終用插入排序将局部有序的數組排序。
在此我們選擇增量 gap=length/2，縮小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 來表示。
如圖示例：
（1）初始增量第一趟 gap = length/2 = 4
（2）第二趟，增量縮小為 2
（3）第三趟，增量縮小為 1,得到最終排序結果
源碼包下載下傳：Download
最内層循環其實就是插入排序:
public class ShellSort {
//核心代碼---開始
public static void sort(Comparable[] arr) {
int j;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
Comparable tmp = arr[i];
for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
}
//核心代碼---結束
public static void main(String[] args) {
int N = 2000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
ShellSort.sort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}