概述

　　希尔排序法(缩小增量法) 属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

　　把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

实现过程

　　先取一个正整数d1小于n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2小于d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

　　例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82 
25 59 94 65 23 
45 27 73 25 39 
10

然后我们对每列进行排序：

10 14 73 25 23 
13 27 94 33 39 
25 59 94 65 82 
45

　　将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73 
25 23 13 
27 94 33 
39 25 59 
94 65 82 
45

排序之后变为：

10 14 13 
25 23 33 
27 25 59 
39 65 73 
45 94 82 
94

最后以1步长进行排序（此时就是简单的插入排序了）。

实现效率

　　希尔排序是一个不稳定的排序，其时间复杂度受步长（增量）的影响。

　　空间复杂度：　Ｏ(1)

　　时间复杂度：　平均 O(n^1.3) 
最好　O(n) 
最坏　O(n^2)

Java实现

public static void shellSort(int[] a) {
        int gap = 1, i, j, len = a.length;
        int temp;//插入排序交换值的暂存
        //确定初始步长
        while (gap < len / 3){
            gap = gap * 3 + 1;
        }
        for (; gap > 0; gap /= 3){//循环遍历步长，最后必为1
            for (i = gap; i < len; i++) {//每一列依次向前做插入排序
                temp = a[i];
                //每一列中在a[i]上面且比a[i]大的元素依次向下移动
                for (j = i - gap; j >= 0 && a[j] > temp; j -= gap){
                    a[j + gap] = a[j];
                }
                //a[i]填补空白，完成一列中的依次插入排序
                a[j + gap] = temp;
            }
        }   
    }

http://blog.csdn.net/amazing7/article/details/51386145