轉(zhuǎn)自：
http://blog.sina.com.cn/s/blog_61e439e50100mfe8.html
希爾排序(shellsort)又叫增量遞減(diminishing increment)排序，是由D.L. Shell發(fā)明的，這個算法是通過一個逐漸減小的增量使一個數(shù)組逐漸趨近于有序從而達(dá)到排序的目的，該算法由1959年公布。
最差時間復(fù)雜度：根據(jù)步長序列的不同而不同。已知最好的: O(nlog2n)
最優(yōu)時間復(fù)雜度：O(n)
平均時間復(fù)雜度：根據(jù)步長序列的不同而不同。
原始的算法實現(xiàn)在最壞的情況下需要進(jìn)行O(n2)的比較和交換。V. Pratt的書[1] 對算法進(jìn)行了少量修改，可以使得性能提升至O(n log2 n)。這比最好的比較算法的O(n log n)要差一些。
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進(jìn)一大步。然后算法再取越來越大的步長進(jìn)行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）。
假設(shè)有一個很小的數(shù)據(jù)在一個已按升序排好序的數(shù)組的末端。如果用復(fù)雜度為O(n2)的排序（冒泡排序或插入排序），可能會進(jìn)行n次的比較和交換才能將該數(shù)據(jù)移至正確位置。而希爾排序會用較大的步長移動數(shù)據(jù)，所以小數(shù)據(jù)只需進(jìn)行少數(shù)比較和交換即可到正確位置。
一個更好理解的希爾排序?qū)崿F(xiàn)：將數(shù)組列在一個表中并對列排序（用插入排序）。重復(fù)這過程，不過每次用更長的列來進(jìn)行。最后整個表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身僅僅對原數(shù)組進(jìn)行排序（通過增加索引的步長，例如是用i += step_size而不是i++）。
例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進(jìn)行排序，我們可以通過將這列表放在有5行的表中來更好地描述算法，這樣他們就應(yīng)該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每行進(jìn)行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
當(dāng)我們以單行來讀取數(shù)據(jù)時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經(jīng)移至正確位置了，然后再以3為步長進(jìn)行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)椋?/font>
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進(jìn)行排序（此時就是簡單的插入排序了）。
步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。算法最開始以一定的步長進(jìn)行排序。然后會繼續(xù)以一定步長進(jìn)行排序，最終算法以步長為1進(jìn)行排序。當(dāng)步長為1時，算法變?yōu)椴迦肱判颍@就保證了數(shù)據(jù)一定會被排序。
算法如下
#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;
}