簡介
希爾排序(縮小增量法) 屬于插入類排序,由Shell提出，希爾排序對直接插入排序進行了簡單的改進：它通過加大插入排序中元素之間的間隔，并在這些有間隔的元素中進行插入排序，從而使數據項大跨度地移動，當這些數據項排過一趟序之后，希爾排序算法減小數據項的間隔再進行排序，依次進行下去，進行這些排序時的數據項之間的間隔被稱為增量，習慣上用字母h來表示這個增量。
常用的h序列由Knuth提出，該序列從1開始，通過如下公式產生：
|
1
|
h = 3 * h +1 |
反過來程序需要反向計算h序列，應該使用
|
1
|
h=(h-1)/3 |
代碼實現
實現代碼1：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public static void shellSort(int[] arr){ int temp; for (int delta = arr.length/2; delta>=1; delta/=2){ //對每個增量進行一次排序 for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //注意每個地方增量和差值都是delta temp = arr[j-delta]; arr[j-delta] = arr[j]; arr[j] = temp; } }//loop i }//loop delta} |
實現代碼2：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public static void shellSort2(int[] arr){ int delta = 1; while (delta < arr.length/3){//generate delta delta=delta*3+1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ... } int temp; for (; delta>=1; delta/=3){ for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ temp = arr[j-delta]; arr[j-delta] = arr[j]; arr[j] = temp; } }//loop i }//loop delta} |
上面程序在和直接插入法比較，會發現其與直接插入排序的差別在于：直接插入排序中的h會以1代替。
Shell排序是不穩定的，它的空間開銷也是O(1),時間開銷估計在O(N3/2)~O(N7/6)之間。
