希尔排序是对插入排序的改进。插入排序是前面元素已经有序了，移动元素是一个一个一次往后移动，当插入的元素比前面排好序的所有元素都小时，则需要将前面所有元素都往后移动。希尔排序有了自己的增量，可以理解为插入排序的增量为1，希尔排序增量是gap。代码就是在插入排序代码的基础上多了一层增量变化的循环。可以参考http://www.cnblogs.com/chengxiao/p/6104371.html，博主作了详尽介绍。
public static void shellSort(int[] a){
int j;
for(int gap=a.length/2;gap>0;gap/=2)
for(int i=gap;i<a.length;i++){
int tmp=a[i];
for(j=i;j>=gap&&tmp<a[j-gap];j-=gap)
a[j]=a[j-gap];
a[j]=tmp;
}
}