希尔排序是冲破二次时间屏障的第一批算法之一。
它是通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到最后一趟（比较相邻元素）为止。因此希尔排序也叫缩减增量排序。
希尔排序使用一个序列h1，h2,h3...hk来排序。
具体的意思是
第一趟排序比较的是相隔为hk的元素，也就是比较a[i]与a[i+hk],保证a[i]<=a[i+hk]。
第二次比较的是相隔为hk-1的元素，也就是比较a[i]与a[i+hk-1],保证a[i]<=a[i+hk-1]。
直到最后比较的是相隔之间为h1的元素。.
因此这个序列也叫增量序列，这个排序算法也叫缩减增量排序。
只要h1等与1，任何增量序列都是可以的。（也就是最后一定是比较相邻之间的元素）
具体看一下java的算法实现：
package k;
import java.util.Scanner;
/**
* 希尔排序
* @author TangZH
*
*/
public class ShellSort {
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
String str[]=in.nextLine().split("\\s+");
int inter[]=new int[str.length];
for(int i=0;i<str.length;i++)
{
inter[i]=Integer.valueOf(str[i]);
}
ShellSort(inter);
outPut(inter);
}
/**
* 希尔排序
* @param inter
*/
private static void ShellSort(int inter[])
{
for(int gap=inter.length/2;gap>0;gap/=2) //gap为hk
{
for(int i=gap;i<inter.length;i++)
{
int j=i;
int temp=inter[i];
for(;j>=gap && temp<inter[j-gap];j-=gap)
inter[j]=inter[j-gap];
inter[j]=temp;
}
}
}
private static void outPut(int []inter)
{
for(int n:inter)
{
System.out.printf("%d ", n);
}
}
}
实现希尔排序的方法是SellSort（int inter[]）;
接下来好好分析一下该算法的每个步骤：
假如输入的是：12 4 6 24 7 12 4 16（此时gap=4，i=4，j=4，temp=inter[4]=7）
1、此时gap=4
那么第一次7与12比较，如果小于就互相交换。
i++，12与4比较，小于就互换，
i++， 4与6比较，小于就互换，
i++，16与24比较，小于就互换。
第一趟之后为： 7 4 4 16 12 12 6 24
2、
7 4 4 16 12 12 6 24
此时gap=2
那么第一次4与7比较，如果小于就互相交换。
4 4 7 16 12 12 6 24
i++，16与4比较，小于就互换，这里16大于4，不变
4 4 7 16 12 12 6 24
i++， 12与7比较，不变，12与4比较，不变
4 4 7 16 12 12 6 24
i++，12与16比较，小于，于是变成 4 4 7 <> 12 16 6 24，12与4比较，大于4，因此12放进16原来在的位置
4 4 7 12 12 16 6 24
同样道理比较相同颜色的元素，进行排序。
.
.
.
第二趟之后为： 4 4 6 12 7 16 12 24
.
.
.
直到gap=1
每一趟的排序结果为（输入为：12 4 6 24 7 12 4 16）
7 4 4 16 12 12 6 24
4 4 6 12 7 16 12 24
4 4 6 7 12 12 16 24
4 4 6 7 12 12 16 24
总而言之：
gap的值就是hk，元素之间的间隔，这道题中gap=4,2,1。最外层的循环是给出gap的值.（每次都除以二），然后在循环里面开始对相隔为gap的元素进行插入排序，直到最后一趟比较相邻之间的元素。
希尔排序的最坏运行时间为O（N^2）.由于Shell算法中增加了一个辅助空间temp，因此算法的辅助空间为S(n)=O(1).Shell排序是不稳定的。