1 #include <stdio.h> 3 void shell_order(int *a,int length) 4 { 5 int increment,i,j,tem; 6 for(increment = length/2; increment > 0; increment /=2) 7 { 8 for(i = increment; i < length; i++) 9 { 10 tem = a[i]; 11 for(j = i; j >= increment; j -= increment) 12 { 13 if(tem<a[j-increment]) 14 a[j] = a[j-increment]; 15 else break; 16 } 17 a[j] = tem; 18 } 19 } 20 } 21 22 int main() 23 { 24 int a[] = {6,5,1,7,2,4,3}; 25 int length = sizeof(a)/sizeof(int); 26 int i; 27 shell_order(a,length); 28 for(i = 0; i < length; i++) 29 printf("%d ",a[i]); 30 printf("\n"); 31 return 0; 32 }
本例代码关于希尔排序的实现：首先选取一个增量的选取方法，然后按照增量的选取规则，每次循环的对数据按照增量的间隔进行插入排序式的排序，其本质就是对独立子数组进行插入排序。
希尔排序：希尔排序的运行时间主要依赖于增量序列的选取，以上例子代码中使用的增量是Shell建议的 h1 = [Length/2]; h2 = [h1/2] ....但是这个增量的选取并不好，而且效率最坏的情况为O(n^2);下边列举一种增量的选取：
（1） Hibbard的增量选取法：1、3、7 ... 2^k-1...;因为这种增量的选取方法，没有公因子，据证明效率为O（N^(3/2)）;但是也有说经过大量的运行这种增量选取的效率为O(N^(5/4));但都比shell增量效率要高；
（2）Sedgewick提出的另一种增量选取：9*4^i-9*2^i + 1或是4^i - 3*4^i + 1;通过这两种选取增量的方法可以实现shell排序平均效率猜想为O(N^(7/6)),已经比Hibbard 的方法效率高了。
关于希尔排序：希尔排序的性能在实践中是完全可以接受的，即使对于数以万计的N仍然是这样，由于编程简单的特点，使得shell排序对应大量的数据输入的常用算法。
