1. 简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

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

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

基本思想

希尔排序的基本思想是：

1. 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
2. 然后逐渐将增量减小,并重复上述过程。
3. 直至增量为1,此时数据序列基本有序,最后进行插入排序。

2. Java实现

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

测试一下:

public static void main(String[] args) {
    int[] arr = new int[100];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * 100);
    }
    shellSort(arr);
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i]);
        System.out.print(' ');
    }
}

3. 复杂度

• 时间复杂度是O(nlogn) ~ O(n²)
• 空间复杂度为常数阶 O(1)