希尔排序

希尔排序（Shellsort）是一种改进的插入排序算法，旨在提高插入排序在大型乱序数组上的效率。插入排序在处理这类数组时效率较低，因为它每次只交换相邻元素，导致元素只能缓慢地从数组一端移动到另一端。希尔排序通过允许交换不相邻的元素，先对数组的局部进行排序，从而加速排序过程，最终再使用插入排序将局部有序的数组完成排序。

核心思想：h-有序数组

希尔排序的关键在于将数组变为 h-有序 的。一个 h-有序数组指的是，数组中所有间隔为 h 的子数组都是有序的。可以将 h-有序数组理解为 h 个相互独立的有序子数组交织而成。

例如，对于一个数组，如果它是 4-有序的，那么以下四个子数组都是有序的：

索引 0, 4, 8, 12, ... 的元素组成的子数组
索引 1, 5, 9, 13, ... 的元素组成的子数组
索引 2, 6, 10, 14, ... 的元素组成的子数组
索引 3, 7, 11, 15, ... 的元素组成的子数组

在排序初期，h 值较大，可以使元素一次性移动较远的距离，快速消除数组中的较大逆序，为后续较小的 h 值排序创造更有序的初始状态。随着 h 值逐渐减小，最后当 h 减小到 1 时，整个数组就变成 1-有序的，即完全有序。

递增序列

希尔排序的效率很大程度上取决于 递增序列 (h 序列) 的选择。递增序列是一系列递减的 h 值，算法会依次使用这些 h 值将数组变为 h-有序。算法中使用的是 1/2(3^k - 1) 序列，从 N/3 开始递减至 1，例如：1, 4, 13, 40, 121, 364, 1093, ...。

选择合适的递增序列是一个复杂的问题，目前没有哪种序列被证明是绝对最优的。算法的性能不仅依赖于 h 值，还与 h 值之间的数学关系有关，例如公因子等。

希尔排序的时间复杂度分析较为复杂，但可以确定的是，它的最坏情况时间复杂度优于平方级别 (O(N²))。对于算法 2.3 的递增序列，最坏情况下的比较次数大约与 N^3/2 成正比。

public class Shell {
    public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1; // 计算递增序列 h = 1, 4, 13, 40, ...
        }
        while (h >= 1) { // 递减 h 值进行排序
            for (int i = h; i < N; i++) {
                // 对每个 h-子数组进行插入排序
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h); // 交换间隔为 h 的元素
                }
            }
            h = h / 3; // 递减 h 值
        }
    }
}

代码解读:

计算递增序列 h: while (h < N/3) h = 3*h + 1; 这段代码计算递增序列的初始最大值 h，确保 h 不超过数组长度的三分之一。
外层循环 while (h >= 1): 控制 h 值递减，从最大值开始，逐步减小到 1。每次循环都进行一次 h-排序。
中间循环 for (int i = h; i < N; i++): 遍历数组，从索引 h 开始，到数组末尾。
内层循环 for (int j = i; j >= h && less(a[j], a[j-h]); j -= h): 这部分代码类似于插入排序，但步长为 h 而不是 1。它将 a[i] 元素插入到其所属的 h-子数组的正确位置。less(a[j], a[j-h]) 比较当前元素 a[j] 和它前面间隔 h 的元素 a[j-h]，如果 a[j] 较小，则交换它们的位置，并将 j 减小 h 继续向前比较，直到 j < h 或 a[j] 不小于 a[j-h]。
h = h / 3;: 在完成一次 h-排序后，将 h 值缩小，准备进行下一轮排序，直到 h 变为 1。