序之希尔排序 
　　　 希尔排序算法因科学家 Donald L. Shell 得名， 它是基于插入排序的， 但增加了一个特性，即增量排序，它在有间隔的元素中进行插入排序，然后减小间隔，直到为间隔1。 比如说先对下标为0,4.8的元素进行排序，然后对下标为 1,5,9的元素排序，接下来减小间隔， 如对 0,1 排序。
　　　 插入排序对基本有序的数组排序效率非常高，然而通常情况下， 如果有小的元素在最后， 则它几乎要移动 N 个位置才能来到前面， 平均也要 N/2 次，对于 N 个数来说， 移动的次数太多了。希尔排序使用增量，让元素可以大跨度地移动， 而不是一个一个地往前移， 那么经过很少次数的移动后， 数组会变成若干个小的基本有序的数组，到最后增量减为1的时候， 每个元素离自己的正确位置不过一两步而已。事实上在最后一步，增量减为1的时候，就是一个普通的插入排序了。刚开始对希尔排序可能不太理解， 但如果将插入排序看作是增量始终为1的希尔排序，则问题就迎刃而解。
　　　 增量的大小对效率的影响非常之大， 可能算法不仅是一种， 但通常认为， 增量序列应该是互质的， 且无论如何，最后都要保证增量的值为1。 Donald E. Knuth 的算法是 h = 3*h +1. 由于这些因素，它的时间复杂度通常在 O(N^2/3) ~ O(N^6/7) 之间。 按最坏的情况算， 接近于O(N^2/3). 

 代码片断
 /*
　based on insert sort, but use a increment value
　between elements, the elements are not compared
　and swaped with the one just next to them, but
　the ones that have a distance between them, the
　distance is decided by the value of increment.
 */
 public void sort () {
　　 int h = 1;　 //设定增量的初始值 

　 // 因为增量不能大小数组的长度，所以 3h+1 <= maxSize
　　 while (h <= (maxSize-1)/3) {　
　　　　 h = 3*h+1;　　　　  　// 按公式得到最大的增量，也即第一个要用的增量
　　 } 

　　 while (h > 0) {　　  　// 增量减到1的时候是最后一次了
　　　　 for (int i = h; i<maxSize; i++) font i="" color="#008000"> // 当增量为1时,就是从第一个开始.
　　　　　　 int tmp = array[i];　　　　　　// 与插入排序相同 

// 从当前元素开始，以一个增量为单位向前跳，直到自己开始的地方为止
　　　　　　 int j = i;
　　　　　　 while ( j>h-1 && array[j-h] >= tmp) {
　　 
　　  // 如果这个元素比自已大，就往后移动一个增量
　　　　　　　　 array[j] = array[j-h];　　 

　　　　　　　　 j = j - h;　　　　　　　　　　  　// 每次递减一个增量
　　　　　　 }
　　　　　　 if ( j != i ) {
　　　　　　　　 array[j] = tmp;　　　　　　　 // 找到了位置就插入
　　　　　　 }   
　　　　 }　  // END WHILE
　　　　 h = (h-1) / 3;　　 // 减小增量值, 由 h = 3h+1 反推而得
　　 }　 // END FOR
 }
 

代码2：
 Code Sample in C
 int n;
 int i,j,gap,temp;
 int a[N]; 

 gap=n/2;
 while (gap>0) {
　　 for(i=gap;i<n;i++)
　　 {
　　　　j=i-gap;
　　　　while (j>=gap)
　　　　　 if(a[j]>a[j+gap])
　　　　　 {
　　　　　　　 temp=a[j];
　　　　　　　 a[j]=a[j+gap];
　　　　　　　 a[j+gap]=temp;
　　　　　　　 j=j-gap;
　　　　　  }
　　　　　  else j=0;
　　 }
　　 gap=gap/2;
　 }