简单插入排序存在一定的问题：
当待插入的数比较小时，会进行多次比较并进行多次的后移赋值操作，影响效率。

希尔排序也是一种插入排序，是希尔（Donald Shell）在1959年提出的一种排序算法。它是简单插入排序经过改进后的一个更高效的版本，也称为缩小增量排序。

希尔排序基本思想

希尔排序是把元素按照下标的增量进行分组，对每组元素直接使用插入排序。这样随着增量的逐步减少，数组会越来越有序，当增量减至1时，执行完该轮排序后，希尔排序结束。

图示与代码

根据对有序序列在插入时采用的方法不同，希尔排序又可分为交换法和移动法。

希尔排序 - 交换法

希尔排序-交换法.png

public class ShellSort {

    public static void main(String[] args) {

        int[] arr = {5, 21, 9, 6, 10, 2, 16};
        int len = arr.length;
        int temp = 0;
        int count = 0;

        System.out.println("原数组：" + Arrays.toString(arr));
        for (int gap = len / 2; gap > 0; gap /= 2) {
            // 分成的组数为gap
            for (int i = gap; i < len; i++) {
                // 遍历各组中所有的元素，步长gap
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 如果当前元素大于加上步长后的那个元素，交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("第"+(++count)+"轮："+Arrays.toString(arr));
        }
    }

}

打印结果：

原数组：[5, 21, 9, 6, 10, 2, 16]
第1轮：[5, 10, 2, 6, 21, 9, 16]
第2轮：[2, 5, 6, 9, 10, 16, 21]

希尔排序 - 移动法

该方法跟交换法大体一样，只是进行组内排序时采用了移动法（可看成一个插入排序）

public class ShellSort1 {

    public static void main(String[] args) {

        int[] arr = {5, 21, 9, 6, 10, 2, 16};
        int len = arr.length;
        int count = 0;

        System.out.println("原数组：" + Arrays.toString(arr));

        // 增量为gap，并逐步缩小增量
        for (int gap = len / 2; gap > 0; gap /= 2) {
            // 从第gap个元素，逐个对其所在组进行直接插入排序
            for (int i = gap; i < len; i++) {
                int j = i;
                int temp = arr[j];
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    // 移动 这里和插入排序是一样的原理
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // while退出后就给temp找到了插入位置
                arr[j] = temp;
            }
            System.out.println("第"+(++count)+"轮："+Arrays.toString(arr));
        }
    }

}