希尔排序(ShellSort)也称“缩小增量排序”，是将整个无序列分割成若干小的子序列分别进行直接插入排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序，这样大大减少了元素移动的次数提高了排序效率。
      希尔排序的过程是: 假定待排序列的数组为R[0…n-1]，先取一个正整数h1(h1  间隔序列的求得: 间隔序列就是在希尔排序中使用的增量的序列。例如，在含有100个数据项的数组中，可能先以40为增量，然后以13为增量，以4为增量，最后以1为增量进行希尔排序。其中[40，13，4，11就是一个间隔序列。

下面介绍两种间隔序列的求得方法:

方法一：

在希尔排序算法中，可以利用公式h=3*h+1 生成序列1，4，13，40等。当间隔数大于数组长度时停止这个过程。例如，对于数组长度为 100 的序列，序系列的第5个数121就超过了数组的长度。因此，使用增量为40作为最大数字来开始这个排序过程，然后每完成一趟排序，用前面提供的公式的倒推式减小间隔: h=(h-1)/3，即按照增量序列为40，13，4，1为增量对序列进行希尔排序。

方法二：

在希尔排序算法中，也可以利用公式n/2 来求得间隔序列。例如，对于数组长度为 100 的序列， 

用此公式求得的序列为50，25，12，6，3，1。这个方法的好处是不需要在排序开始之前去找初始的间隔。

附   件:

点击下载此附件

图   示: