希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。
希尔排序将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，过程中较小的元素，跳跃式的往前移。然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
举个例子，如下：
1 int a[]={2,5,8,4,6,3,1,9,7,55}; 2 int length=sizeof(a)/sizeof(int); 3 int i,j,gap; 4 5 for(gap=length/2; gap>0; gap /= 2)//步长 6 { 7 for(i=gap;i<length;i++) //直接插入排序的gap始终为1 8 { 9 if(a[i]<a[i-gap]) 10 { 11 int key=a[i]; 12 for(j=i-gap;j>=0&&a[j]>key;j-=gap) 13 { 14 a[j+gap]=a[j]; 15 } 16 a[j+gap]=key; 17 } 18 } 19 }
原文：http://www.cnblogs.com/supercell/p/3613700.html