轉自：
http://blog.sina.com.cn/s/blog_61e439e50100mfe8.html
希爾排序(shellsort)又叫增量遞減(diminishing increment)排序，是由D.L. Shell發明的，這個算法是通過一個逐漸減小的增量使一個數組逐漸趨近于有序從而達到排序的目的，該算法由1959年公布。
最差時間復雜度：根據步長序列的不同而不同。已知最好的: O(nlog2n)
最優時間復雜度：O(n)
平均時間復雜度：根據步長序列的不同而不同。
原始的算法實現在最壞的情況下需要進行O(n2)的比較和交換。V. Pratt的書[1] 對算法進行了少量修改，可以使得性能提升至O(n log2 n)。這比最好的比較算法的O(n log n)要差一些。
希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越大的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。
假設有一個很小的數據在一個已按升序排好序的數組的末端。如果用復雜度為O(n2)的排序（冒泡排序或插入排序），可能會進行n次的比較和交換才能將該數據移至正確位置。而希爾排序會用較大的步長移動數據，所以小數據只需進行少數比較和交換即可到正確位置。
一個更好理解的希爾排序實現：將數組列在一個表中并對列排序（用插入排序）。重復這過程，不過每次用更長的列來進行。最后整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身僅僅對原數組進行排序（通過增加索引的步長，例如是用i += step_size而不是i++）。
例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5行的表中來更好地描述算法，這樣他們就應該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每行進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
當我們以單行來讀取數據時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變為：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序（此時就是簡單的插入排序了）。
步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。算法最開始以一定的步長進行排序。然后會繼續以一定步長進行排序，最終算法以步長為1進行排序。當步長為1時，算法變為插入排序，這就保證了數據一定會被排序。
算法如下
#include <stdio.h>
void output_array(int data[], int n)
{
int i;
for(i = 0; i < n; i++)
printf("%d ", data[i]);
printf("\n");
}
void swap(int *a, int *b)
{
int x;
x = *a;
*a = *b;
*b = x;
}
void insertion_sort(int data[], int n, int increment)
{
int i, j;
for(i = increment; i < n; i += increment)
for(j = i; j >= increment && data[j] > data[j - increment]; j -= increment)
swap(&data[j], &data[j - increment]);
}
void shellsort(int data[], int n)
{
int i, j;
for(i = n / 2; i > 2; i /= 2)
for(j = 0; j < i; j++)
insertion_sort(data + j, n - j, i);
insertion_sort(data, n, 1);
}
int main()
{
int data[] = {5, 3, 1, 665, 77, 66, 44, 11, 10, 9, 8, 6};
output_array(data, 12);
shellsort(data, 12);
output_array(data, 12);
return 0;
}