一，希尔排序算法介绍
①希尔排序又称缩小增量排序 ，它本质上是一个插入排序算法。为什么呢？
因为，对于插入排序而言，插入排序是将当前待排序的元素与前面所有的元素比较，而希尔排序是将当前元素与前面增量位置上的元素进行比较，然后，再将该元素插入到合适位置。当一趟希尔排序完成后，处于增量位置上的元素是有序的。
②希尔排序算法的效率依赖于增量的选取
假设增量序列为 h(1)，h(2).....h(k)，其中h(1)必须为1，且h(1)<h(2)<...h(k) 。
第一趟排序时在增量为h(k)的各个元素上进行比较；
第二趟排序在增量为h(k-1)的各个元素上进行比较;
..........
最后一趟在增量h(1)上进行比较。由此可以看出，每进行一趟排序，增量是一个不断减少的过程，因此称之为缩小增量。
当增量减少到h(1)=1时，这里完全就是插入排序了，而在此时，整个元素经过前面的 k-1 趟排序后，已经变得基本有序了，而我们知道，对于插入排序而言，当待排序的数组基本有序时，插入排序的效率是非常高的。因此，希尔排序就是利用“增量”技巧将插入排序的平均时间复杂度O(N^2)降低为亚二次方。
二，希尔排序实例分析
假设原始数组为： 81 94 11 96 12 35 增量序列为 h(1)=1 h(2)=3
这里一共有两个增量序列，故一共有两趟排序。第一趟按照增量3来排序
处于增量3上的元素集合如下：<81 96>，<94 12>，<11 35>排序之后变成：<81 96>，<12 94>，<11 35>
即，数组变成了：81 12 11 96 94 35
可以看出，在增量为3的各个位置上的元素都是有序的。
经过前面一趟排序，此时数组已经基本有序，再使用增量为1的排序时（插入排序），比较的次数将会大大地降低。
第二趟按增量为h(1)=1 来排序，排序后数组变成：
11 12 35 81 94 96
三，算法实现
1 public class ShellSort { 2 3 /** 4 * 使用希尔推荐的增量: h(k)=N/2 , h(i)=h(i+1)/2 5 * @param arr 待排序数组 6 */ 7 public static <T extends Comparable<? super T>> void shellSort(T[] arr){ 8 9 int j; 10 for(int gap = arr.length; gap >= 1; gap /=2)//排序的趟数 11 { 12 13 /*每对增量序列为: 14 * <gap, 0> <gap+1,1> <gap+2,2>.....<arr.length-1, arr.length-1-gap> 15 */ 16 for(int i = gap; i < arr.length; i++)//在"增量位置上" 进行插入排序 17 { 18 T tmp = arr[i]; 19 for(j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j-= gap) 20 arr[j] = arr[j - gap]; 21 arr[j] = tmp; 22 } 23 } 24 } 25 26 //for test purpose 27 public static void main(String[] args) { 28 Integer[] arr = {81,94,11,96,12,35,17,95,28,58,41,75,15}; 29 shellSort(arr); 30 for (Integer integer : arr) { 31 System.out.print(integer + " "); 32 } 33 } 34 }