[数据结构与算法]O(nlogn)级排序之希尔排序

【注】以下代码参考力扣<<排序算法全解析>>
??要更轻松的了解希尔排序，最好先看一下插入排序。
??希尔排序：将一组数按照一定增量间隔分组,比如间隔为5时下标为0,5,10…为一组；下标1,6,11…为一组以此类推，可以将所有数大致分为5组。每一组分别进行插入排序。为使所有数有序，这个增量间隔会按照一定方式变小，当增量间隔为1时，就是所有数的插入排序，但此时绝大部分数已经有序。

public static void shellSort(int[] arr) {
    // gap就是增量间隔
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 下面其实就是每组的插入排序
        for (int i = gap; i < arr.length; i++) {
            //保留当前要插入的值
            int currentNumber = arr[i];
            // 该组前一个数字的索引
            int preIndex = i - gap;
            //确保索引在下标范围内进行比较
            while (preIndex >= 0 && currentNumber < arr[preIndex]) {
                // 前一个数值大则将其向后挪位置
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            // 找到当前要插入值的位置
            arr[preIndex + gap] = currentNumber;
        }
    }
}

排序时使用的增量间隔是有讲究的。比较著名的有：
???Hibbard 增量序列：2^k-1即1,3,7,15…，平均时间复杂度为 O(n^5/4);
???Knuth 增量序列：a₁=1;a_k+1=3*a_k+1，平均时间复杂度为 O(n^3/2);
???Sedgewick 增量序列：部分通过 9?4^k?9?2^k+1 计算出来的，部分是通过 4^k?3?2^k+1 计算出来的，平均时间复杂度为 O(n^7/6);

以 Knuth 增量序列为例：

public static void shellSortByKnuth(int[] arr) {
    // 找到当前数组需要用到的 Knuth 序列中的最大值
    int maxKnuthNumber = 1;
    while (maxKnuthNumber <= arr.length / 3) {
        maxKnuthNumber = maxKnuthNumber * 3 + 1;
    }
    // 增量按照 Knuth 序列规则依次递减
    for (int gap = maxKnuthNumber; gap > 0; gap = (gap - 1) / 3) {
        for (int i = gap; i < arr.length; i++) {
            int currentNumber = arr[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && currentNumber < arr[preIndex]) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            arr[preIndex + gap] = currentNumber;
        }
    }
}

??之前介绍的冒泡排序、插入排序、选择排序都是将相邻元素进行比较，最多只能消除一对逆序对。而希尔排序中每组元素的间隔随增量间隔变化，间隔远则可能一次消除多个逆序对，这就是希尔排序时间复杂度降低的原因。希尔排序的时间复杂度实际在O(n)和O(n^2)之间，空间复杂度为O(n)，但是希尔排序是不稳定的。