本文實例講述了Java排序算法總結之希爾排序。分享給大家供大家參考。具體分析如下：
前言：希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。本文主要介紹希爾排序用Java是怎樣實現的。
希爾排序(縮小增量法) 屬于插入類排序,是將整個無序列分割成若干小的子序列分別進行插入排序。希爾排序并不穩定，O(1)的額外空間，時間復雜度為O(N*(logN)^2)。最壞的情況下的執行效率和在平均情況下的執行效率相比相差不多。
基本思想：
先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
代碼實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
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]; // 計算下一個欲進行處理的位置 Pointer = 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(""); } } DataLength = DataLength / 2; // 計算下次分割的間隔長度 } } } |
希爾排序幾乎沒有最壞情況，無論是正序、逆序、亂序，所用時間都不是很多，附加儲存是O(1)，的確非常不錯。在沒搞清楚快速排序、堆排序之前，它的確是個很好的選擇。希望能給你帶來幫助。
希望本文所述對大家的java程序設計有所幫助。
