簡單插入排序存在一定的問題：
當(dāng)待插入的數(shù)比較小時(shí)，會進(jìn)行多次比較并進(jìn)行多次的后移賦值操作，影響效率。

希爾排序也是一種插入排序，是希爾（Donald Shell）在1959年提出的一種排序算法。它是簡單插入排序經(jīng)過改進(jìn)后的一個(gè)更高效的版本，也稱為縮小增量排序。

希爾排序基本思想

希爾排序是把元素按照下標(biāo)的增量進(jìn)行分組，對每組元素直接使用插入排序。這樣隨著增量的逐步減少，數(shù)組會越來越有序，當(dāng)增量減至1時(shí)，執(zhí)行完該輪排序后，希爾排序結(jié)束。

圖示與代碼

根據(jù)對有序序列在插入時(shí)采用的方法不同，希爾排序又可分為交換法和移動法。

希爾排序 - 交換法

希爾排序-交換法.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("原數(shù)組：" + Arrays.toString(arr));
        for (int gap = len / 2; gap > 0; gap /= 2) {
            // 分成的組數(shù)為gap
            for (int i = gap; i < len; i++) {
                // 遍歷各組中所有的元素，步長gap
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 如果當(dāng)前元素大于加上步長后的那個(gè)元素，交換
                    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));
        }
    }

}

打印結(jié)果：

原數(shù)組：[5, 21, 9, 6, 10, 2, 16]
第1輪：[5, 10, 2, 6, 21, 9, 16]
第2輪：[2, 5, 6, 9, 10, 16, 21]

希爾排序 - 移動法

該方法跟交換法大體一樣，只是進(jìn)行組內(nèi)排序時(shí)采用了移動法（可看成一個(gè)插入排序）

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("原數(shù)組：" + Arrays.toString(arr));

        // 增量為gap，并逐步縮小增量
        for (int gap = len / 2; gap > 0; gap /= 2) {
            // 從第gap個(gè)元素，逐個(gè)對其所在組進(jìn)行直接插入排序
            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));
        }
    }

}