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

基本思想：

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

代碼實(shí)現(xiàn)：

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

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

【編輯推薦】

1. 何時(shí)創(chuàng)建Java對(duì)象實(shí)例
2. 經(jīng)典四講貫通C++排序之二 希爾排序
3. Java Web應(yīng)用開(kāi)發(fā)中的一些概念解讀