Shell Sort C语言实现

void Shellsort(int a[],int n){
	int increment,i,j,tmp;
	for(increment  = n/2;increment>0;increment /= 2){
		for(i = increment;i<n;i++){
			tmp = a[i];
			for(j = i;j>=increment&&a[j-increment]>tmp;j -= increment)
				a[j] = a[j - increment];
			a[j] = tmp;
		}
	}
}
           

关于步长序列的讨论

以上是以n/2,n/4,...,1的序列分组，后面的分组会覆盖前面的分组的情形，是比较差的分组

比较好的分组有素数组

Hibbard’sIncrement Sequence hk = 2^k -1 worst case O(N^(3/2)) average case O(N^(5/4))

Sedgewick’s best sequence is {1, 5, 19, 41, 109, … } in which the terms are either ofthe form 9*4^i – 9*2^i + 1 or

4^i –3*2^i + 1. Tavg( N )= O ( N^(7/6)) and Tworst( N )= O ( N^(4/3)).