希爾排序(縮小增量法) 屬于插入類排序,是將整個無序列分割成若干小的子序列分別進行插入排序。希爾排序并不穩定，O(1)的額外空間，時間復雜度為O(N*(logN)^2)。最壞的情況下的執行效率和在平均情況下的執行效率相比相差不多。

基本思想：

先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

代碼實現：

public class Test {   
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 預設數據數組   
public static void main(String args[]) {   
int i; // 循環計數變量   
int Index = a.length;// 數據索引變量   
System.out.print("排序前: ");   
for (i = 0; i < Index - 1; i++)   
System.out.printf("%3s ", a);   
System.out.println("");   
ShellSort(Index - 1); // 選擇排序   
// 排序后結果   
System.out.print("排序后: ");   
for (i = 0; i < Index - 1; i++)   
System.out.printf("%3s ", a);   
System.out.println("");   
}   
public static void ShellSort(int Index) {   
int i, j, k; // 循環計數變量   
int Temp; // 暫存變量   
boolean Change; // 數據是否改變   
int DataLength; // 分割集合的間隔長度   
int Pointer; // 進行處理的位置   
DataLength = (int) Index / 2; // 初始集合間隔長度   
while (DataLength != 0) // 數列仍可進行分割   
{   
// 對各個集合進行處理   
for (j = DataLength; j < Index; j++) {   
Change = false;   
Temp = a[j]; // 暫存Data[j]的值,待交換值時用   
Pointer = j - DataLength; // 計算進行處理的位置   
// 進行集合內數值的比較與交換值   
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {   
a[Pointer + DataLength] = a[Pointer];   
// 計算下一個欲進行處理的位置   
PointerPointer = Pointer - DataLength;   
Change = true;   
if (Pointer < 0 || Pointer > Index)   
break;   
}   
// 與最后的數值交換   
a[Pointer + DataLength] = Temp;   
if (Change) {   
// 打印目前排序結果   
System.out.print("排序中: ");   
for (k = 0; k < Index; k++)   
System.out.printf("%3s ", a[k]);   
System.out.println("");   
}   
}   
DataLengthDataLength = DataLength / 2; // 計算下次分割的間隔長度   
}   
}   
} 

希爾排序幾乎沒有最壞情況，無論是正序、逆序、亂序，所用時間都不是很多，附加儲存是O(1)，的確非常不錯。在沒搞清楚快速排序、堆排序之前，它的確是個很好的選擇。希望能給你帶來幫助。

【編輯推薦】

1. 何時創建Java對象實例
2. 經典四講貫通C++排序之二 希爾排序
3. Java Web應用開發中的一些概念解讀