一、希尔排序介绍

希尔排序这个名字，来源于它的发明者希尔，也称作“缩小增量排序”，是插入排序的一种更高效的改进版本。

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

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的数组，对比插入排序和希尔排序的性能：

四、适用场景

希尔排序是对直接插入排序的一种优化，可以用于大型的数组，希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。