一、希爾排序介紹

希爾排序這個名字，來源于它的發明者希爾，也稱作“縮小增量排序”，是插入排序的一種更高效的改進版本。

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

1、插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率

2、但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位

二、對數組使用希爾排序

1. 首先，選擇增量 gap = 10/2 ，縮小增量繼續以 gap = gap/2 的方式
2. 初始增量為 gap = 10/2 = 5，整個數組分成了 5 組
3. 按顏色劃分為【 8 , 3 】，【 9 , 5 】，【 1 , 4 】，【 7 , 6 】，【 2 , 0】
4. 對這分開的 5 組分別使用插入排序
5. 結果可以發現，這五組中的相對小元素都被調到前面了
6. 縮小增量 gap = 5/2 = 2，整個數組分成了 2 組
7. 【 3 , 1 , 0 , 9 , 7 】，【 5 , 6 , 8 , 4 , 2 】
8. 對這分開的 2 組分別使用上節所講的插入排序
9. 此時整個數組的有序性是很明顯的
10. 再縮小增量 gap = 2/2 = 1，整個數組分成了 1 組
11. 【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0 】
12. 此時，只需要對以上數列進行簡單的微調，不需要大量的移動操作即可完成整個數組的排序

‍

public static void shellSort(Comparable[] arr) {
    int j;
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            Comparable tmp = arr[i];
            for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = tmp;
        }
    }
}

復習插入排序

private static void sort(Comparable[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j > 0; j--) {
            if (arr[j].compareTo(arr[j - 1]) < 0) {
                swap(arr, j, j - 1);
            } else {
                break;
            }
        }
    }
}

private static void swap(Object[] arr, int i, int j) {
    Object t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

三、時間復雜度

性能比較

隨機生成長度為100的數組，對比插入排序和希爾排序的性能：

四、適用場景

希爾排序是對直接插入排序的一種優化，可以用于大型的數組，希爾排序比插入排序和選擇排序要快得多，并且數組越大，優勢越大。