Java排序算法 希爾排序

希爾排序(Shell

Sort)是插入排序的一種。是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。本文主要介紹希爾排序用Java是怎樣實作的。

AD：

希爾排序(縮小增量法)

屬于插入類排序,是将整個無序列分割成若幹小的子序列分别進行插入排序。希爾排序并不穩定，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("排序後: "); 

}   

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]); 

DataLengthDataLength = DataLength / 2; // 計算下次分割的間隔長度 

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