思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。
說明：
（1）子序列的構成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。由於這個原因，希爾排序也叫縮小增量排序。
（2）優點：讓關鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。
（3）希爾排序的一個重要性質是，一個h(k)排序的文件保持它的h(k)排序性，否則該算法沒有任何意義，因為前面各趟排序的結果會被後面各趟排序給打亂。
（4）增量排序的一種流行（但是不好）的選擇是使用Shell建議的序列：h(t)=N/2，h(k)=h(k+1)/2。
（5）時間復雜度及穩定性分析：
1）對特定的待排序對象序列，可以准確地估算關鍵碼的比較次數和對象移動次數。但想要弄清關鍵碼比較次數和對象移動次數與增量選擇之間的依賴關系，並給出完整的數學分析，還沒有人能夠做到。
2）希爾排序的時間復雜度小於O(N2)，大於O(NlogN)。
3）希爾排序不穩定。
（6）希爾排序是算法非常簡單且又具有極其復雜的分析的好例子。它的性能在實踐中完全可以接受，即使是對於數以萬計的N仍是如此。編程的簡單特點使它成為對適度地大量的輸入數據經常選用的算法。
1 #include <stdio.h>
2
3 void ShellSort(int arr[], int len)
4 {
5 if (!arr || len == 0)
6 {
7 return;
8 }
9
10 int h, i, j, tmp;
11 for (h = len / 2; h > 0; h /= 2)
12 {
13 for (i = h; i < len; i++)
14 {
15 tmp = arr[i];
16 for (j = i; j >= h; j -= h)
17 {
18 if (arr[j - h] > tmp)
19 {
20 arr[j] = arr[j - h];
21 }
22 else
23 {
24 break;
25 }
26 }
27 arr[j] = tmp;
28 }
29 }
30 return;
31 }
32
33 int main(void)
34 {
35 int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
36 ShellSort(arr, 10);
37
38 for (int i = 0; i < 10; i++)
39 {
40 printf("%d ", arr[i]);
41 }
42 printf("\n");
43
44 return 0;
45 }
