OI-wiki 希尔排序缩小增量排序全解算法原理、复杂度证明与 C/Python 实现【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki希尔排序Shell sort是 OI-wiki 基础算法 章节中对 插入排序 的一种重要改进版本其核心思想是先宏观粗排、再微观细排通过逐步缩小的间隔对不相邻元素进行插入排序从而把插入排序的 $O(n^2)$ 复杂度大幅压低。阅读本文后你将掌握希尔排序的定义、完整执行流程、稳定性与空间复杂度结论、两种经典间距序列下的时间复杂度$O(n^{3/2})$ 与 $O(n\log^2 n)$及其背后的整套数学证明并可直接运行文中给出的 C 与 Python 实现。定义希尔排序英语Shell sort也称为缩小增量排序法是插入排序的一种改进版本。希尔排序以它的发明者希尔英语Donald Shell命名。它与普通插入排序最根本的区别在于排序对不相邻的记录进行比较和移动。普通插入排序参见 docs/basic/code/insertion-sort/insertion-sort_1.cpp每次只比较相邻元素一趟只能让元素移动一个位置而希尔排序通过加大比较和移动的步长让元素可以大步跨越从而在宏观上先接近有序为后续的插入排序创造良好条件——正如插入排序中所述插入排序在数列几乎有序时效率很高。过程希尔排序将排序过程分为三个阶段循环进行将待排序序列分为若干子序列每个子序列的元素在原始数组中间距相同对这些子序列进行插入排序减小每个子序列中元素之间的间距重复上述过程直至间距减少为 $1$。当间距最终为 $1$ 时整个序列就是普通插入排序但由于此前各轮粗排已经让序列接近有序最后一轮插入排序只需极少的移动即可完成。这也解释了希尔排序为什么能以插入排序为基座却获得更优的复杂度。性质稳定性希尔排序是一种不稳定的排序算法。这一点在 排序简介 中也有明确归纳该页将常见排序按稳定性分类明确指出选择排序、堆排序、快速排序、希尔排序不是稳定排序。直观原因是希尔排序在按较大间隔分组排序时会把相隔较远的相等元素跨组交换从而可能改变相等元素的原始相对顺序。对比之下插入排序 是稳定排序但希尔排序为了获得更好的时间复杂度付出了稳定性的代价。时间复杂度希尔排序的最优时间复杂度为 $O(n)$——当输入序列本来就接近有序时各轮插入排序几乎不需要移动元素。希尔排序的平均时间复杂度和最坏时间复杂度与间距序列gap sequence的选取有关。设间距序列为 $H$下面给出 $H$ 的两种经典选取方式这两种选取方式均使得排序算法的复杂度降为 $o(n^2)$ 级别。命题 1若间距序列为 $H { 2^k-1\mid k1,2,\ldots,\lfloor\log_2 n\rfloor }$从大到小则希尔排序算法的时间复杂度为 $O(n^{3/2})$。命题 2若间距序列为 $H { k2^p\cdot 3^q\mid p,q\in \mathbb N,k\le n }$从大到小则希尔排序算法的时间复杂度为 $O(n\log^2 n)$。需要说明的是命题 2 中的间距序列 $H{2^p\cdot 3^q}$ 与下文实现章节给出的 $h3h1$Knuth 序列并不相同二者属于不同的间距选取策略实现章节采用的是更常见的 Knuth 序列其工程实现简单、实际表现良好但上文给出的两个渐近复杂度结论分别对应这两种数学上可严格证明的序列。为证明这两个命题我们先给出一个重要的定理并证明它这个定理反映了希尔排序的最主要特征。定理 1只要程序执行了一次 $\text{InsertionSort}(h)$不管之后怎样调用 $\text{InsertionSort}$ 函数$A$ 数组怎样变换下列性质均会被一直保持$$ \begin{array}{c} A_1,A_{1h},A_{12h},\ldots \ A_2,A_{2h},A_{22h},\ldots \ \vdots \ A_h,A_{hh},A_{h2h},\ldots \end{array} $$即一旦以 $h$ 为间隔完成了插入排序这 $h$ 个子列每个子列内部元素间隔 $h$的有序性在后续所有排序操作中都不会被破坏。这个成果保持性质是希尔排序能够压低复杂度的关键。接下来我们证明定理 1。我们先证明引理 1。引理 1对于整数 $n,m$、正整数 $l$ 与两个数组 $X(x_1,x_2,\ldots,x_{nl}),Y(y_1,y_2,\ldots,y_{ml})$满足如下要求$$ y_1 \le x_{n1},y_2 \le x_{n2},\ldots,y_l \le x_{nl} $$则我们将两个数组分别升序排序后上述要求依然成立。引理 1 证明设数组 $X$ 排序完为数组 $X(x1,\ldots,x{nl})$数组 $Y$ 排序完为数组 $Y(y1,\ldots,y{ml})$。对于任何 $1\le i\le l$$x_{ni}$ 小等于数组 $X$ 中的 $l-i$ 个元素也小等于数组 $X$ 中的 $l-i$ 个元素这是因为 $X$ 与 $X$ 的元素可重集合是相同的。那么在可重集合 ${x_{n1},\ldots,x_{nl} } \subset X$ 中大等于 $x_{ni}$ 的元素个数不超过 $l-i$ 个。进而小于 $x{ni}$ 的元素个数至少有 $i$ 个取出其中的 $i$ 个设它们为 $x{nk_1},x_{nk_2},\ldots,x_{nk_i}$。于是有$$ y_{k_1}\le x_{nk_1}\le x{ni},y{k_2}\le x_{nk_2}\le x{ni},\ldots,y{k_i}\le x_{nk_i}\le x_{ni} $$所以 $x_{ni}$ 至少大于等于 $Y$ 也即 $Y$ 中的 $i$ 个元素那么自然有 $yi\le x{ni},(1\le i\le l)$。再回到原命题的证明我们实际上只需要证明调用完 $\text{InsertionSort}(h)$ 的紧接着下一次调用 $\text{InsertionSort}(k)$ 后$h$ 个子列仍有序即可之后容易用归纳法得出。下面只考虑下一个调用执行完 $\text{InsertionSort}(h)$ 后如下组已经完成排序$$ \begin{array}{c} A_1,A_{1h},A_{12h},\ldots \ A_2,A_{2h},A_{22h},\ldots \ \vdots \ A_h,A_{hh},A_{h2h},\ldots \end{array} $$而之后执行 $\text{InsertionSort}(k)$则会将如下组排序$$ \begin{array}{c} A_1,A_{1k},A_{12k},\ldots \ A_2,A_{2k},A_{22k}, \ldots \ \vdots \ A_k,A_{kk},A_{k2k},\ldots \end{array} $$对于每个 $i$ $(1\le i\le \min(h,k))$考虑如下两个组$$ \begin{array}{c} A_i,A_{ik},A_{i2k},\ldots \ \ldots,A_{ih},A_{ihk},A_{ih2k},\ldots \end{array} $$第二个组前面也加上「$\ldots$」的原因是可能 $ih\ge k$ 从而前面也有元素。则第二个组就是引理 1 中的 $X$ 数组第一个组就是 $Y$ 数组$l$ 就是第二个组从 $ih$ 之后顶到末尾的长度$n$ 是第二个组中前面那个「$\ldots$」的长度$m$ 是第一个组去掉前 $l$ 个后剩下的个数。又因为有$$ A_i\le A_{ih},A_{ik}\le A_{ihk},\ldots $$所以由引理 1 可得执行 $\text{InsertionSort}(k)$ 将两个组分别排序后这个关系依然满足即依然有 $A_i\le A_{ih},(1\le i\le \min(h,k))$。若有 $i\min(h,k)$容易发现取正整数 $w$ $(1\le w\le \min(h,k))$ 再加上若干个 $k$ 即可得到 $i$则之前的情况已经蕴含了此情况的证明。综合以上论述便有执行完 $\text{InsertionSort}(k)$ 依然有 $A_i\le A_{ih},(1\le i\le n-h)$。因此定理 1 得证。这个定理揭示了希尔排序在特定集合 $H$ 下可以优化复杂度的关键因为在整个过程中它可以一致保持前面的成果不被摧毁即 $h$ 个子列分别有序从而使后面的调用中指针 $i$ 的移动次数大大减少。接下来我们单拎出来一个数论引理进行证明。这个定理在 OI 界因小凯的疑惑一题而大为出名。而在希尔排序复杂度的证明中它也使得定理 1 得到了很大的扩展。引理 2若 $a,b$ 均为正整数且互素则不在集合 ${axby\mid x,y\in \mathbb N }$ 中的最大正整数为 $ab-a-b$。引理 2 证明分两步证明先证明方程 $axbyab-a-b$ 没有 $x,y$ 均为非负整数的解若无非负整数的限制容易得到两组解 $(b-1,-1),(-1,a-1)$。通过其通解形式 $xx_0tb,yy_0-ta$容易得到上面两组解是「相邻」的因为 $b-1-b-1$。当 $t$ 递增时$x$ 递增$y$ 递减所以如果方程有非负整数解必然会夹在这两组解中间但这两组解「相邻」中间没有别的解。故不可能有非负整数解。再证明对任意整数 $c ab-a-b$方程 $axbyc$ 有非负整数解我们找一组解 $(x_0,y_0)$ 满足 $0\le x_0 b$由通解的表达式这可以做到。则有$$ by_0c-ax_0\ge c-a(b-1)ab-a-b-aba-b $$所以 $b(y_01) 0$又因为 $b0$所以 $y_010$所以 $y_0\ge 0$。所以 $(x_0,y_0)$ 为一组非负整数解。综上得证。而下面这个定理则揭示了引理 2 是如何扩展定理 1 的。定理 2如果 $\gcd(h_{t1},h_t)1$则程序先执行完 $\text{InsertionSort}(h_{t1})$ 与 $\text{InsertionSort}(h_t)$ 后执行 $\text{InsertionSort}(h_{t-1})$ 的时间复杂度为 $O\left(\dfrac{nh_{t1}h_t}{h_{t-1}} \right)$且对于每个 $j$其 $i$ 的移动次数是 $O\left(\dfrac{h_{t1}h_t}{h_{t-1}} \right)$ 级别的。定理 2 证明对于 $j\le h_{t1}h_t$ 的部分$i$ 的移动次数显然是 $O\left(\dfrac{h_{t1}h_t}{h_{t-1}} \right)$ 级别的。故以下假设 $jh_{t1}h_t$。对于任意的正整数 $k$ 满足 $1\le k\le j-h_{t1}h_t$注意到$h_{t1}h_t-h_{t1}-h_th_{t1}h_t\le j-k\le j-1$又因为 $\gcd(h_{t1},h_t)1$故由引理 2得存在非负整数 $a,b$使得$ah_{t1}bh_tj-k$。即得$$ kj-ah_{t1}-bh_t $$由定理 1得$$ A_{j-bh_t}\le A_{j-(b-1)h_t}\le \ldots\le A_{j-h_t}\le A_j $$与$$ A_{j-bh_t-ah_{t1}}\le A_{j-bh_t-(a-1)h_{t1}}\le \ldots\le A_{j-bh_t-h_{t1}}\le A_{j-bh_t} $$综合以上既有$A_kA_{j-ah_{t1}-bh_t}\le A_j$。所以对于任何 $1\le k\le j-h_{t1}h_t$有 $A_k\le A_j$。在 Shell-Sort 伪代码中 $i$ 指针每次减 $h_{t-1}$减 $O\left(\dfrac{h_{t1}h_t}{h_{t-1}} \right)$ 次即可使得 $i\le j-h_{t1}h_t$进而有 $A_i\le A_j$不满足 while 循环的条件退出。证明完对于每个 $j$ 的移动复杂度后即可得到总的时间复杂度$$ \sum_{jh_{t-1}1}^n{O\left(\frac{h_{t1}h_t}{h_{t-1}} \right)}O\left(\frac{nh_{t1}h_t}{h_{t-1}}\right) $$得证。认真观察定理 2 的证明过程可以发现定理 1 可以进行「线性组合」即 $A$ 以 $h$ 为间隔有序以 $k$ 为间隔亦有序则以 $h$ 和 $k$ 的非负系数线性组合仍是有序的。而这种「线性性」即是由引理 2 保证的——只要 $\gcd(h_{t1},h_t)1$那么足够大的下标差 $j-k$ 总可以写成 $ah_{t1}bh_t$ 的形式从而把任意远处的元素也纳入有序性比较的范围。有了这两个定理我们可以证明命题 1 与 2。命题 1 证明间距序列 $H\{2^k-1\}$复杂度 $O(n^{3/2})$将 $H$ 写为序列的形式$$ H(h_11,h_23,h_37,\ldots,h_{\lfloor \log_2 n\rfloor}2^{\lfloor \log_2 n\rfloor}-1) $$Shell-Sort 执行顺序为$\text{InsertionSort}(h_{\lfloor \log_2 n\rfloor}),\text{InsertionSort}(h_{\lfloor \log_2 n\rfloor-1}),\ldots,\text{InsertionSort}(h_2),\text{InsertionSort}(h_1)$.分两部分去分析复杂度对于前面的若干个满足 $h_t\ge \sqrt{n}$ 的 $h_t$显然有 $\text{InsertionSort}(h_t)$ 的时间复杂度为 $O\left(\dfrac{n^2}{h_t} \right)$。考虑对最接近 $\sqrt{n}$ 的项 $h_k$有$$ O\left(\frac{n^2}{h_t} \right)O(n^{3/2}) $$而对于 $i k$ 的 $h_i$因为有 $2h_i h_{i1}$所以可得$$ O\left(\frac{n^2}{h_i} \right)O(n^{3/2}/2^{i-k}),(ik) $$所以大等于 $\sqrt n$ 部分的总时间复杂度为$$ \sum_{ik}^{\lfloor \log_2 n\rfloor}{O(n^{3/2}/2^{i-k})}O(n^{3/2}) $$对于后面剩下的满足 $h_t \sqrt{n}$ 的项前两项的复杂度还是 $O(n^{3/2})$而对于后面的项 $h_t$有定理 2 可得时间复杂度为$$ O\left(\frac{nh_{t2}h_{t1}}{h_t} \right)O\left(\frac{nh_{t2}\cdot h_{t2}/2}{h_{t2}/4} \right)O(nh_{t2}) $$再次利用 $2h_i h_{i1}$ 性质可得此部分总时间复杂度为下式中 $k$ 沿用了上一种情况中的含义$$ 2O(n^{3/2})\sum_{i1}^{k-3}{O(nh_{i1})}O(n^{3/2})\sum_{i1}^{k-3}{O(nh_{k-1}/2^{k-i-3})}O(n^{3/2})O(nh_{k-1})O(n^{3/2}) $$综上可得总时间复杂度即为 $O(n^{3/2})$。命题 2 证明间距序列 $H\{2^p\cdot 3^q\}$复杂度 $O(n\log^2 n)$注意到一个事实如果已经执行过了 $\text{InsertionSort}(2)$ 与 $\text{InsertionSort}(3)$那么因为 $2\cdot 3-2-31$所以由定理 2每个元素只有与它相邻的前一个元素可能大于它之前的元素全部都小于它。于是 $i$ 指针只需要最多两次就可以退出 while 循环。也就是说此时再执行 $\text{InsertionSort}(1)$复杂度降为 $O(n)$。更进一步如果已经执行过了 $\text{InsertionSort}(4)$ 与 $\text{InsertionSort}(6)$我们考虑所有的下标为奇数的元素组成的子列与下标为偶数的元素组成的子列。则这相当于把这两个子列分别执行 $\text{InsertionSort}(2)$ 与 $\text{InsertionSort}(3)$。那么也是一样这时候再执行 $\text{InsertionSort}(2)$相当于对两个子列分别执行 $\text{InsertionSort}(1)$也只需要两个序列和的级别即 $O(n)$ 的复杂度就可以将数组变为 $2$ 间隔有序。不断归纳就可以得到如果已经执行过了 $\text{InsertionSort}(2h)$ 与 $\text{InsertionSort}(3h)$则执行 $\text{InsertionSort}(h)$ 的复杂度也只有 $O(n)$。接下来分为两部分分析复杂度对于 $h_tn/3$ 的部分则执行每个 $\text{InsertionSort}(h_t)$ 的复杂度为 $O(n^2/h_t)$。而 $n^2/h_t3n$所以单词插入排序复杂度为 $O(n)$。而这一部分元素个数是 $O(\log^2 n)$ 级别的所以这一部分时间复杂度为 $O(n\log^2 n)$。对于 $h_t\le n/3$ 的部分因为 $3h_t\le n$所以这之前已经执行了 $\text{InsertionSort}(2h_t)$ 与 $\text{InsertionSort}(3h_t)$于是执行 $\text{InsertionSort}(h_t)$ 的时间复杂度是 $O(n)$。还是一样的这一部分元素个数也是 $O(\log^2 n)$ 级别的所以这一部分时间复杂度为 $O(n\log^2 n)$。综上可得总时间复杂度即为 $O(n\log^2 n)$。空间复杂度希尔排序的空间复杂度为 $O(1)$——它完全在原数组上进行就地排序in-place各轮分组排序仅交换数组内元素不依赖任何与 $n$ 同阶的辅助存储结构。实现OI-wiki 在 docs/basic/shell-sort.md 中直接给出了 C 与 Python 两种实现二者采用同一间距策略Knuth 序列即从 $h1$ 起按 $h3h1$ 递增取小于 $n/3$ 的最大值作为初始间距再按 $h\lfloor h/3\rfloor$ 递减。这样生成的间距序列如 $1,4,13,40,121,\ldots$相邻项互素且覆盖从大到小的全部步长在工程上实现简单、实测表现良好。 Ccpp template typename T void shell_sort(T array[], int length) { int h 1; while (h length / 3) { h 3 * h 1; } while (h 1) { for (int i h; i length; i) { for (int j i; j h array[j] array[j - h]; j - h) { std::swap(array[j], array[j - h]); } } h h / 3; } } Pythonpython def shell_sort(array, length): h 1 while h length / 3: h int(3 * h 1) while h 1: for i in range(h, length): j i while j h and array[j] array[j - h]: array[j], array[j - h] array[j - h], array[j] j - h h int(h / 3) 代码逐段解读间距初始化h从 $1$ 开始不断执行 $h3h1$直到h length / 3为止。这里取小于 $n/3$作为停止条件是经验性的选择保证初始间距不会超过数组长度的三分之一避免第一轮分组过疏、子序列过短而失去意义。外层 whileh 1控制间距从大到小逐轮收缩直至 $h1$ 完成最后一轮普通插入排序。每轮结束后h h / 3C 整型除法向下取整Python 用int(h / 3)等价实现。中层 fori从h到length-1依次把每个元素当作新牌插入到以 $h$ 为间隔的前方有序子列中。这保证了每一轮下来$h$ 个子列 $A_r,A_{rh},A_{r2h},\ldots$$r1,\ldots,h$各自有序正是定理 1 描述的成果保持特征。内层 for/whilej从i起以h为步长递减array[j] array[j - h]时交换并继续前移直至找到正确插入位置。这正是对不相邻记录进行比较和移动的直接实现——它本质上是把 docs/basic/code/insertion-sort/insertion-sort_1.cpp 中相邻比较的j--换成步长h的j - h。为什么最后要保留 $h1$ 的一轮当 $h1$ 时内层循环退化为标准的相邻插入排序。理论上此前各轮已经让数组接近有序最后一轮插入排序只需极少量移动即可完成整体复杂度因此被大幅压低。这正是定理 2 与命题 1、2 的证明所揭示的机制保持前面各轮成果不被破坏使得后续轮次中指针 $i$ 的移动次数被限制在很小的范围内。应用场景与注意事项适用前提希尔排序适用于对就地排序$O(1)$ 额外空间有要求、且元素可比较的中等规模数据。它不需要像归并排序那样开辟辅助数组也不需要像快速排序那样担心递归栈或最坏情况的退化。稳定性限制希尔排序不稳定若业务要求保持相等元素的相对顺序例如多关键字排序的次要关键字应改用稳定排序见 排序简介 中关于稳定性的分类。复杂度上限基于比较的排序算法时间复杂度下限是 $O(n\log n)$参见 docs/basic/complexity.md 关于渐近符号与复杂度下界的讨论。命题 2 给出的 $O(n\log^2 n)$ 已经非常接近该下界但希尔排序的平均复杂度与间距序列的选择紧密相关实际选用的间距序列不同性能差异可能很大文中两个渐近结论分别对应两种可严格证明的序列选取切勿想当然地推广到任意间距序列。在 OI/ICPC 中的定位希尔排序通常作为理解插入排序改进思路与复杂度证明方法的教学素材竞赛中大规模数据排序一般直接使用std::sort等内建排序。但本章证明中出现的定理 2 与引理 2互素数的不能表示的最大数问题本身具有独立的数论价值值得单独掌握。参考资料与注释希尔排序的命名与基础定义参见维基百科希尔排序词条本页 C 实现亦以该词条为参考来源对应原文注释 [^ref1]。排序的稳定性分类与整体介绍参见 排序简介。插入排序的伪代码、性质与三种语言实现参见 插入排序 及 插入排序 C 实现、插入排序 Python 实现。渐近符号大 $O$、$\Theta$、$\Omega$、$o$、$\omega$的严格定义参见 复杂度。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考