假设有一个数组int data[16] = {...}。 首先将这个增量设为16 / 2 = 8, 这样就将这个数组分成了8个子数组,它们的索引是0, 8 1, 9 2, 10等等 。对这些子数组进行排序。然后再使增量为8 / 2 = 4,这样就将原数组分成了4个子数组,它们的索引分别是0, 4, 8, 12 1, 5, 9, 13等等。再对这四组数进行排序,直到增量为1。
以上所描述的增量递减只是一种方法,这种方法并不是最有效率的。如f(n) = 3 * f(n - 1) + 1 f(1) = 1 (..., 121, 40, 13, 4, 1)就比上面的取增量的方法好。这种方法的时间复杂度是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://www.cnblogs.com/nokiaguy/archive/2008/05/15/1199359.html