希爾排序(shellsort)又叫增量遞減(diminishing increment)排序，是由D.L. Shell發(fā)明的，這個(gè)算法是通過一個(gè)逐漸減小的增量使一個(gè)數(shù)組逐漸趨近于有序從而達(dá)到排序的目的。
假設(shè)有一個(gè)數(shù)組int data[16] = {...}。 首先將這個(gè)增量設(shè)為16 / 2 = 8，
這樣就將這個(gè)數(shù)組分成了8個(gè)子數(shù)組，它們的索引是0, 8 1, 9 2, 10等等 。對這些子數(shù)組進(jìn)行排序。然后再使增量為8 / 2
= 4，這樣就將原數(shù)組分成了4個(gè)子數(shù)組，它們的索引分別是0, 4, 8, 12 1, 5, 9,
13等等。再對這四組數(shù)進(jìn)行排序，直到增量為1。
以上所描述的增量遞減只是一種方法，這種方法并不是最有效率的。如f(n) = 3 * f(n - 1) + 1 f(1) = 1 (..., 121, 40， 13, 4, 1)就比上面的取增量的方法好。這種方法的時(shí)間復(fù)雜度是
O(n ^1.5)。
算法如下
#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;
}
新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining