希爾排序?qū)τ诙噙_(dá)幾千個數(shù)據(jù)項的，中等大小規(guī)模的數(shù)組排序表現(xiàn)良好，希爾排序不像快速排序和其它時間復(fù)雜度為O（n*logn)的排序算法那么快，因此，對非常大的文件排序，它不是最優(yōu)選擇，但是希爾排序比選擇排序和插入排序這種時間復(fù)雜度為O(n²)的排序要快的多，并且它非常容易實現(xiàn)，代碼簡短
希爾排序也是插入排序的一種，在插入排序中，如果最小的數(shù)在最后面，則復(fù)制的次數(shù)太多，而希爾解決了這個問題，它也是n-增量排序，它的思想是通過加大插入排序中元素的間隔，并在這些有間隔的元素中進(jìn)行插入排序，當(dāng)這些數(shù)據(jù)項排過一趟序后，希爾排序算法減小數(shù)據(jù)項的間隔再進(jìn)行排序，依此進(jìn)行下去。進(jìn)行這些排序時數(shù)據(jù)項之間的間隔被稱為增量，并且習(xí)慣上用字母h來表示。
對于某個馬上要進(jìn)行希爾排序的數(shù)組，開始的間隔應(yīng)該更大，然后間隔不段減小，直到間隔變?yōu)?.
間隔序列：
間隔序列中的數(shù)字素質(zhì)通常被認(rèn)為很重要-除了1之外它們沒有公約數(shù)，這個約束條件使每趟排序更有可能保持前一趟排序已排好的效果，對于不同的間隔序列，有一個絕對的條件，就是逐漸減小的間隔最后一定要等于1.因此最后一趟是一次普通的插入排序。
下面列出的例子是h=h*3+1的規(guī)律得出的：
|
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
|
package com.jll.sort;public class ShellSort { int[] arr; int size; public ShellSort() { super(); } public ShellSort(int size) { this.size = size; arr = new int[size]; } /** * @param args */ public static void main(String[] args) { ShellSort ss = new ShellSort(10); for(int i=0;i<10;i++){ ss.arr[i] = (int) ((Math.random()*100)+1); System.out.print(ss.arr[i]+" "); } ss.shellSort(); System.out.println(); System.out.println("after sort:"); for(int i=0;i<10;i++){ System.out.print(ss.arr[i]+" "); } } public void shellSort(){ int h = 1; while(h<=size/3){ h = h*3+1; } for(;h>0;h=(h-1)/3){ for(int i=h;i<size;i++){ int temp = arr[i]; int j = i; while(j>h-1&&arr[j-h]>temp){ arr[j]=arr[j-h]; j-=h; } arr[j]=temp; } } } } |
