一、思想
希爾排序：使數組中任意間隔為h的元素都是有序的。在進行排序的時候，如果h很大，我們就能將元素移動到很遠的地方，為實現更小的h有序創造方便。用這種方式，對任意以1結尾的h序列，我們都能夠將數據排序；
二、概念
h有序數組：任意間隔為h的元素都是有序的數組；
三、高效原因
對于大規模亂序數組插入排序很慢，因為它只會交換相鄰的元素，因此元素只能一點一點地從數組的一端移動到另一段；
希爾排序更高效的原因：它權衡了子數組的規模和有序性，在排序之初，各個子數組都很短；在排序之后子數組都是部分有序的，這兩種情況很適合插入排序；
四、代碼
|
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
|
/** * 希爾排序 * * @author pengcx * */public class Shell extends Sort { public static void main(String[] args) { String[] a = { "d", "a", "w", "b", "q" }; Shell.sort(a); show(a); } /** * 排序數組a * * @param a * 排序的數組a */ protected static void sort(Comparable[] a) { int N = a.length; int h = 1; while (h < N / 3) { h = 3 * h + 1; } while (h >= 1) { for (int i = 0; i < N; i++) { for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) { exch(a, j, j - h); } } h = h / 3; } } } |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
