希尔排序不是一次性按相邻元素比较，而是先按"间隔 $gap$"分组，组内做插入排序；随后逐渐缩小 $gap$，直到 $gap=1$。

Ph1zの理解： 普通插入排序只能一个一个挪，遇到逆序对就慢得要命。希尔排序的妙处在于——先大步跳着排，把远处的逆序对快速消除；再小步走，把细节理顺。就像整理书架，先把明显放错位置的大部头搬好，再微调每本书的位置。

代码

void shellSort(int a[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int key = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > key) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = key;
        }
    }
}

正确性证明

希尔排序的正确性基于"每次增量排序后，间隔为 gap 的子序列有序"。

• 对固定 gap，把数组拆成多个长度约为 $n/gap$ 的子序列。
• 对每个子序列做插入排序，保证该子序列内部有序。
• 当 gap 逐步缩小到 1 时，最终整个数组仍由插入排序保证有序。

Ph1zの理解： 最后一步 $gap=1$ 就是普通插入排序。但此时数组已经经过大步长的预处理，远处的逆序对已经很少了，所以这趟插入排序非常快——这就是希尔排序比纯插入排序快的根本原因。

因此在最后一轮 gap = 1 时，数组是有序的。 ✓

复杂度分析

希尔排序的复杂度依赖于增量序列。常见的 $gap=n/2,n/4,\dots ,1$（Shell 原始序列），复杂度通常在 $O(n^{1.5})$ 到 $O(n^2)$ 之间，最坏可能达到 $O(n^2)$。

增量序列的选择很关键：

增量序列	最坏时间复杂度	说明
Shell 原始：$n/2,n/4,\dots ,1$	$O(n^2)$	简单但不够优
Hibbard：$2^k-1$	$O(n^{1.5})$	常用，效果不错
Sedgewick	$O(n^{4/3})$	更优，工程常用
Pratt（所有 $2^p{3}^q$）	$O(n{\log }^{2}n)$	接近最优但序列太长

空间复杂度： $O(1)$。

稳定性： 不稳定。因为元素可能跨不同 gap 距离移动，破坏原等值元素的相对顺序。