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