基本思想:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。
假如步长为4,排序过程可以看成(0,4,8)(1,5,9)(2,6)(3,7)这4组分别排序,具体过程如下:
这样做的目的是为了减少插入排序移动元素的数目,因为这样操作以后数据是几乎排序好的(almost sort)。
步长计算公式h=h*3+1,从h=1开始计算这次计算出的h作为下次步长h,知道h大于要排序的数的个数。如有120个数,当h=40时,h=40*3+1=121>120,则最终步长为40。则每次步长为(40,13,4,1)
java代码实现
public void sort(int[] a)
{
int arrLength=a.length;
int inner,outer;
int temp;
//1 找到最大步长
int h=1;
while(h<=arrLength/3)
h=h*3+1; //(1,4,13,40,123,...)
//2减小步长,直到h=1
while(h>0)
{
//排序一个步长h中的数
for(outer=h;outer<arrLength;outer++)
{
temp=a[outer];
inner=outer;
while(inner>h-1 && a[inner-h]>=temp)
{
a[inner]=a[inner-h];
inner=inner-h;
} //end while
a[inner]=temp;
} //end for
//减小步长
h=(h-1)/3;
} //end while(h>0)
}