java代码
public static void sort(Comparable[] a)
{
int N = a.length;
h = 1;
while(h < N/3) h = h*3 + 1;//步长可为1,4,13,40,121.......
while(h >= 1)
{
for (int i = h; i < N; i++)
{
for (int j = i; j >= h &&less(a[j], a[j - h]); j -= h)//函数less(a,b)比较a,b的大小，a<b返回YES
exch(a, j, j - h);//交换数组a中a[j],a[j-h]两个元素的位置
}
h = h/3;
}
}
解释
希尔排序是一个基于插入排序的改进型插入排序算法。由于插入排序一次只能交换相邻的元素，因此元素只能一点点的从数组的一端移动到另一端。如果最小的元素在数组的末尾的话，那就需要N-1次移动，因此对于插入排序的效率是非常低的。
- 希尔排序的思想是使数组中任意间隔为h的元素是有序的。这样的数组也称为h有序数组，也即一个数组是h个互相独立的有序数组编制在一起组成的数组。如图1所示为一个h有序数组包含了4个有序子数组。
图1:一个h有序数组包含的4个有序子数组
排序算法解析
以步长h=2*h+1(即h为1，3，7...)对图2输入数列进行排序为例，解析希尔算法的步骤。
注意：实际就是a[0]和a[h]比较，a[1]和a[h+1]比较。。。每比较完一轮后，就缩小h的值。
图2:输入数组
- 根据
while(h < N/2) h = h*2 + 1;得到步长h=7， - 第一轮排序，间隔为7的两个元素比较，如果符合交换条件就交换数组a中a[j],a[j-h]两个元素的位置，得到结果如图3所示。
for (int i = 7; i < N; i++)
{
for (int j = i; j >= h &&less(a[j], a[j - h]); j -= h)//如果a[j]小于a[j - h]
exch(a, j, j - h); // 就交换数组a中a[j],a[j-h]两个元素的位置
}
图3:步长为7的排序结果
- 第一轮排序结束后，缩小步长h，此时h=3;
-
继续比较，与步骤2相似，得到结果如图4所示
图4:步长为3的排序结果 -
继续缩小步长h，重复步骤4，（最后这一步的排序也就是普通的插入排序）得到结果如图5所示
图5:步长为1的排序结果 -
虽然插入的效率不高，但是插入排序在对几乎已经排好序的数据操作时，效率却非常高。得到结果如图6所示。
图6：排序结果
希尔排序动态图
图8：以23, 10, 4, 1的步长序列进行希尔排序
