希尔排序的原理：将待排序数据元素集合按照一定的大小分块在块间的数据按照增量（步长）进行直接插入排序，然后根据一定的规则减少步长，再进行一次直接插入排序，直到步长小于1 。

希尔排序需要注意的是最后的增量一定是1 。

下面先给出Java实现代码：

public static void shellSort(int array[]) {
        if (null == array || 1 >= array.length)
            return;
        int step = 0, n = array.length, temp, j;
        int len = n;
        do {
            step = (int) Math.sqrt(n);
            for (int i = step; i < len; i++) {
                temp = array[i];
                j = i - step;
                while (j >= 0 && temp < array[j]) {
                    array[j + step] = array[j];
                    j -= step;
                }
                array[j + step] = temp;
            }
            n = step;
        } while (step > 1);
    }

for (int i = step; i < len; i++) {
                temp = array[i];
                j = i - step;
                while (j >= 0 && temp < array[j]) {
                    array[j + step] = array[j];
                    j -= step;
                }
                array[j + step] = temp;
            }

集合R = {37, 40, 38, 42, 461, 5, 7, 9, 12}
第一趟排序取步长 step = 3 ，

途中使用了三种不同的标记，表示了步长中的每一个元素{Ri ， Ri+1 ， ... Ri+step -1} 。

第二趟排序取步长step = Math.sqrt(3) = 1 ;

得到最后排好序的序列： 5 ， 7， 9，12， 37， 38，42，61 。

在上面的例子中比较特殊，之进行了两趟排序就完成了，而且每趟排序中元素个数都是相同的。而在实际使用中一般step取值为：

step = step/2.2 ;

希尔排序的时间复杂度：O(N^3/2)  到 O(N^7/6) .

希尔排序（Shell Sort）