希爾排序對于多達幾千個數據項的，中等大小規模的數組排序表現良好，希爾排序不像快速排序和其它時間復雜度為O（n*logn)的排序算法那么快，因此，對非常大的文件排序，它不是最優選擇，但是希爾排序比選擇排序和插入排序這種時間復雜度為O(n²)的排序要快的多，并且它非常容易實現，代碼簡短
希爾排序也是插入排序的一種，在插入排序中，如果最小的數在最后面，則復制的次數太多，而希爾解決了這個問題，它也是n-增量排序，它的思想是通過加大插入排序中元素的間隔，并在這些有間隔的元素中進行插入排序，當這些數據項排過一趟序后，希爾排序算法減小數據項的間隔再進行排序，依此進行下去。進行這些排序時數據項之間的間隔被稱為增量，并且習慣上用字母h來表示。
對于某個馬上要進行希爾排序的數組，開始的間隔應該更大，然后間隔不段減小，直到間隔變為1.
間隔序列：
間隔序列中的數字素質通常被認為很重要-除了1之外它們沒有公約數，這個約束條件使每趟排序更有可能保持前一趟排序已排好的效果，對于不同的間隔序列，有一個絕對的條件，就是逐漸減小的間隔最后一定要等于1.因此最后一趟是一次普通的插入排序。
下面列出的例子是h=h*3+1的規律得出的：
|
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; } } } } |
