希尔排序本页面将简要介绍希尔排序．
定义希尔排序（Shell sort），也称为缩小增量排序法，是 插入排序 的一种改进版本．希尔排序以它的发明者希尔（Donald Shell）命名．
过程排序对不相邻的记录进行比较和移动：
将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；对这些子序列进行插入排序；减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 11．为便于分析，下面给出单次间距为 ℎh 的插入排序伪代码，记为 InsertionSort(ℎ)InsertionSort(h)．数组 𝐴A 的下标从 11 到 𝑛n，𝑣v 保存当前待插入的值；希尔排序按间距从大到小调用这一过程．
1𝐟𝐨𝐫 𝑗←ℎ+1 𝐭𝐨 𝑛2𝑣←𝐴𝑗3𝑖←𝑗−ℎ4𝐰𝐡𝐢𝐥𝐞 𝑖≥1 𝐚𝐧𝐝 𝐴𝑖>𝑣5𝐴𝑖+ℎ←𝐴𝑖6𝑖←𝑖−ℎ7𝐴𝑖+ℎ←𝑣1for j←h+1 to n2v←Aj3i←j−h4while i≥1 and Ai>v5Ai+h←Ai6i←i−h7Ai+h←v性质稳定性希尔排序是一种不稳定的排序算法．
时间复杂度希尔排序的最好时间依赖间距序列和是否提前退出；下面给出的没有提前退出的 3ℎ +13h+1 实现最好为 Θ(𝑛log𝑛)Θ(nlogn)．
希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取有关．设间距序列为 𝐻H，下面给出 𝐻H 的两种经典选取方式，这两种选取方式均使得排序算法的复杂度降为 𝑜(𝑛2)o(n2) 级别．
命题 1 若间距序列为 𝐻 ={2𝑘 −1 ∣𝑘 =1,2,…,⌊log2𝑛⌋}H={2k−1∣k=1,2,…,⌊log2n⌋}（从大到小），则希尔排序算法的时间复杂度为 𝑂(𝑛3/2)O(n3/2)．
命题 2 若间距序列为 𝐻 ={𝑘 =2𝑝 ⋅3𝑞 ∣𝑝,𝑞 ∈ℕ,𝑘 ≤𝑛}H={k=2p⋅3q∣p,q∈N,k≤n}（从大到小），则希尔排序算法的时间复杂度为 𝑂(𝑛log2𝑛)O(nlog2n)．
为证明这两个命题，我们先给出一个重要的定理并证明它，这个定理反映了希尔排序的最主要特征．
定理 1 只要程序执行了一次 InsertionSort(ℎ)InsertionSort(h)，不管之后怎样调用 InsertionSortInsertionSort 函数，𝐴A 数组怎样变换，下列每个子序列均保持有序：
𝐴1,𝐴1+ℎ,𝐴1+2ℎ,…𝐴2,𝐴2+ℎ,𝐴2+2ℎ,…⋮𝐴ℎ,𝐴ℎ+ℎ,𝐴ℎ+2ℎ,…A1,A1+h,A1+2h,…A2,A2+h,A2+2h,…⋮Ah,Ah+h,Ah+2h,…接下来我们证明定理 1．
我们先证明引理 1．
引理 1 对于非负整数 𝑛,𝑚n,m、正整数 𝑙l 与两个数组 𝑋(𝑥1,𝑥2,…,𝑥𝑛+𝑙),𝑌(𝑦1,𝑦2,…,𝑦𝑚+𝑙)X(x1,x2,…,xn+l),Y(y1,y2,…,ym+l)，满足如下要求：
𝑦1≤𝑥𝑛+1,𝑦2≤𝑥𝑛+2,…,𝑦𝑙≤𝑥𝑛+𝑙y1≤xn+1,y2≤xn+2,…,yl≤xn+l 则我们将两个数组分别升序排序后，上述要求依然成立．
引理 1 证明 设数组 𝑋X 排序完为数组 𝑋′(𝑥′1,…,𝑥′𝑛+𝑙)X′(x1′,…,xn+l′)，数组 𝑌Y 排序完为数组 𝑌′(𝑦′1,…,𝑦′𝑚+𝑙)Y′(y1′,…,ym+l′)．
对任意 1 ≤𝑖 ≤𝑙1≤i≤l，𝑋X 中严格大于 𝑥′𝑛+𝑖xn+i′ 的元素至多有 𝑙 −𝑖l−i 个．所以在选定的 𝑙l 个元素 {𝑥𝑛+1,…,𝑥𝑛+𝑙}{xn+1,…,xn+l} 中，至少有 𝑖i 个不大于 𝑥′𝑛+𝑖xn+i′．记为 𝑥𝑛+𝑘1,…,𝑥𝑛+𝑘𝑖xn+k1,…,xn+ki，结合原配对不等式可得：
𝑦𝑘1≤𝑥𝑛+𝑘1≤𝑥′𝑛+𝑖,𝑦𝑘2≤𝑥𝑛+𝑘2≤𝑥′𝑛+𝑖,…,𝑦𝑘𝑖≤𝑥𝑛+𝑘𝑖≤𝑥′𝑛+𝑖yk1≤xn+k1≤xn+i′,yk2≤xn+k2≤xn+i′,…,yki≤xn+ki≤xn+i′ 所以 𝑥′𝑛+𝑖xn+i′ 至少大于等于 𝑌Y 也即 𝑌′Y′ 中的 𝑖i 个元素，那么自然有 𝑦′𝑖 ≤𝑥′𝑛+𝑖 (1 ≤𝑖 ≤𝑙)yi′≤xn+i′(1≤i≤l)．
再回到原命题的证明．设数组长度为 𝑁N，我们只需证明 InsertionSort(𝑘)InsertionSort(k) 会保持已有 ℎh 的有序性，再对调用次数归纳即可．这里 ℎ,𝑘h,k 为任意正整数．若 ℎ ≥𝑁h≥N，没有需要检查的相距 ℎh 的元素对，结论显然成立．以下设 ℎ <𝑁h 记调用前后的数组分别为 𝐴A 与 𝐴′A′．调用前有 𝐴𝑖 ≤𝐴𝑖+ℎAi≤Ai+h，其中 1 ≤𝑖 ≤𝑁 −ℎ1≤i≤N−h．对每个 1 ≤𝑤 ≤min(𝑘,𝑁 −ℎ)1≤w≤min(k,N−h)，按带余除法写成 𝑤+ℎ=𝑣+𝑡𝑘,1≤𝑣≤𝑘,𝑡≥0．w+h=v+tk,1≤v≤k,t≥0．考虑从下标 𝑤w 和 𝑣v 开始、间距为 𝑘k 的两个完整子序列： 𝑌=(𝐴𝑤,𝐴𝑤+𝑘,𝐴𝑤+2𝑘,…),𝑋=(𝐴𝑣,𝐴𝑣+𝑘,𝐴𝑣+2𝑘,…)．Y=(Aw,Aw+k,Aw+2k,…),X=(Av,Av+k,Av+2k,…)．设满足 𝑤 +ℎ +𝑗𝑘 ≤𝑁w+h+jk≤N 的非负整数 𝑗j 共有 𝑙l 个．于是 𝑋X 的长度为 𝑡 +𝑙t+l，𝑌Y 的长度至少为 𝑙l；由原来的 ℎh 有序性，𝑌Y 的前 𝑙l 项与 𝑋X 的后 𝑙l 项满足 𝑦𝑗+1=𝐴𝑤+𝑗𝑘≤𝐴𝑤+ℎ+𝑗𝑘=𝑥𝑡+𝑗+1,0≤𝑗<𝑙．yj+1=Aw+jk≤Aw+h+jk=xt+j+1,0≤j 𝐴′𝑤+𝑗𝑘≤𝐴′𝑤+ℎ+𝑗𝑘,0≤𝑗<𝑙．Aw+jk′≤Aw+h+jk′,0≤j 这个定理揭示了希尔排序在特定集合 𝐻H 下可以优化复杂度的关键，因为在整个过程中，它可以一直保持此前各子序列有序的性质，从而使后面的调用中，指针 𝑖i 的移动次数大大减少． 接下来我们单拎出来一个数论引理进行证明．这个定理在 OI 界因 小凯的疑惑 一题而大为出名．而在希尔排序复杂度的证明中，它也使得定理 11 得到了很大的扩展． 引理 2 若 𝑎,𝑏 ≥2a,b≥2 均为整数且互素，则不在集合 {𝑎𝑥 +𝑏𝑦 ∣𝑥,𝑦 ∈ℕ}{ax+by∣x,y∈N} 中的最大正整数为 𝑎𝑏 −𝑎 −𝑏ab−a−b． 引理 2 证明 分两步证明： 先证明方程 𝑎𝑥 +𝑏𝑦 =𝑎𝑏 −𝑎 −𝑏ax+by=ab−a−b 没有 𝑥,𝑦x,y 均为非负整数的解： 若无非负整数的限制，容易得到两组解 (𝑏 −1, −1),( −1,𝑎 −1)(b−1,−1),(−1,a−1)． 通过其通解形式 𝑥 =𝑥0 +𝑡𝑏,𝑦 =𝑦0 −𝑡𝑎x=x0+tb,y=y0−ta，容易得到上面两组解是「相邻」的（因为 𝑏 −1 −𝑏 = −1b−1−b=−1）． 当 𝑡t 递增时，𝑥x 递增，𝑦y 递减，所以如果方程有非负整数解，必然会夹在这两组解中间，但这两组解「相邻」，中间没有别的解． 故不可能有非负整数解． 再证明对任意整数 𝑐 >𝑎𝑏 −𝑎 −𝑏c>ab−a−b，方程 𝑎𝑥 +𝑏𝑦 =𝑐ax+by=c 有非负整数解： 我们找一组解 (𝑥0,𝑦0)(x0,y0) 满足 0 ≤𝑥0 <𝑏0≤x0 则有： 𝑏𝑦0=𝑐−𝑎𝑥0≥𝑐−𝑎(𝑏−1)>𝑎𝑏−𝑎−𝑏−𝑎𝑏+𝑎=−𝑏by0=c−ax0≥c−a(b−1)>ab−a−b−ab+a=−b 所以 𝑏(𝑦0 +1) >0b(y0+1)>0，又因为 𝑏 >0b>0，所以 𝑦0 +1 >0y0+1>0，所以 𝑦0 ≥0y0≥0． 所以 (𝑥0,𝑦0)(x0,y0) 为一组非负整数解． 综上得证． 而下面这个定理则揭示了引理 22 是如何扩展定理 11 的． 定理 2 设 ℎ𝑡+1 >ℎ𝑡 >ℎ𝑡−1ht+1>ht>ht−1 为正整数．如果 gcd(ℎ𝑡+1,ℎ𝑡) =1gcd(ht+1,ht)=1，则程序先执行完 InsertionSort(ℎ𝑡+1)InsertionSort(ht+1) 与 InsertionSort(ℎ𝑡)InsertionSort(ht) 后，执行 InsertionSort(ℎ𝑡−1)InsertionSort(ht−1) 的时间复杂度为 𝑂(𝑛ℎ𝑡+1ℎ𝑡ℎ𝑡−1)O(nht+1htht−1)，且对于每个 𝑗j，其 𝑖i 的移动次数是 𝑂(ℎ𝑡+1ℎ𝑡ℎ𝑡−1)O(ht+1htht−1) 级别的． 定理 2 证明 以下 𝐴A 表示调用 InsertionSort(ℎ𝑡−1)InsertionSort(ht−1) 前的数组．固定外层循环的下标 𝑗j，待插入的值为 𝑣 =𝐴𝑗v=Aj． 对于 𝑗 ≤ℎ𝑡+1ℎ𝑡j≤ht+1ht 的部分，𝑖i 的移动次数显然是 𝑂(ℎ𝑡+1ℎ𝑡ℎ𝑡−1)O(ht+1htht−1) 级别的． 故以下假设 𝑗 >ℎ𝑡+1ℎ𝑡j>ht+1ht． 对于任意的正整数 𝑘k 满足 1 ≤𝑘 ≤𝑗 −ℎ𝑡+1ℎ𝑡1≤k≤j−ht+1ht，注意到：ℎ𝑡+1ℎ𝑡 −ℎ𝑡+1 −ℎ𝑡 <ℎ𝑡+1ℎ𝑡 ≤𝑗 −𝑘 ≤𝑗 −1ht+1ht−ht+1−ht 又因为 gcd(ℎ𝑡+1,ℎ𝑡) =1gcd(ht+1,ht)=1，故由引理 22，得存在非负整数 𝑎,𝑏a,b，使得：𝑎ℎ𝑡+1 +𝑏ℎ𝑡 =𝑗 −𝑘aht+1+bht=j−k． 即得： 𝑘=𝑗−𝑎ℎ𝑡+1−𝑏ℎ𝑡k=j−aht+1−bht 由定理 11，得： 𝐴𝑗−𝑏ℎ𝑡≤𝐴𝑗−(𝑏−1)ℎ𝑡≤…≤𝐴𝑗−ℎ𝑡≤𝐴𝑗Aj−bht≤Aj−(b−1)ht≤…≤Aj−ht≤Aj 与 𝐴𝑗−𝑏ℎ𝑡−𝑎ℎ𝑡+1≤𝐴𝑗−𝑏ℎ𝑡−(𝑎−1)ℎ𝑡+1≤…≤𝐴𝑗−𝑏ℎ𝑡−ℎ𝑡+1≤𝐴𝑗−𝑏ℎ𝑡Aj−bht−aht+1≤Aj−bht−(a−1)ht+1≤…≤Aj−bht−ht+1≤Aj−bht 综合以上即有：𝐴𝑘 =𝐴𝑗−𝑎ℎ𝑡+1−𝑏ℎ𝑡 ≤𝐴𝑗Ak=Aj−aht+1−bht≤Aj． 所以对于任何 1 ≤𝑘 ≤𝑗 −ℎ𝑡+1ℎ𝑡1≤k≤j−ht+1ht，有 𝐴𝑘 ≤𝐴𝑗Ak≤Aj． 在 𝑣v 所属子序列的已处理前缀中，只有原下标位于 (𝑗 −ℎ𝑡+1ℎ𝑡,𝑗)(j−ht+1ht,j) 内的元素可能大于 𝑣v，这样的元素至多有 ⌈ℎ𝑡+1ℎ𝑡ℎ𝑡−1⌉⌈ht+1htht−1⌉ 个．此前的插入只将该子序列的前缀排序，因此，在上面的伪代码中，𝑖i 每次减 ℎ𝑡−1ht−1，越过这些元素后就会遇到不大于 𝑣v 的元素或越过数组左端，从而退出 while 循环．移动次数为 𝑂(ℎ𝑡+1ℎ𝑡ℎ𝑡−1)O(ht+1htht−1)． 证明完对于每个 𝑗j 的移动复杂度后，即可得到总的时间复杂度： 𝑛∑𝑗=ℎ𝑡−1+1𝑂(ℎ𝑡+1ℎ𝑡ℎ𝑡−1)=𝑂(𝑛ℎ𝑡+1ℎ𝑡ℎ𝑡−1)∑j=ht−1+1nO(ht+1htht−1)=O(nht+1htht−1) 得证． 认真观察定理 22 的证明过程，可以发现：定理 1 可以进行「线性组合」，即 𝐴A 以 ℎh 为间隔有序，以 𝑘k 为间隔亦有序，则以 ℎh 和 𝑘k 的非负系数线性组合仍是有序的．而这种「线性性」即是由引理 22 保证的． 有了这两个定理，我们可以证明命题 11 与 22． 命题 1 证明 将 𝐻H 写为序列的形式： 𝐻(ℎ1=1,ℎ2=3,ℎ3=7,…,ℎ⌊log2𝑛⌋=2⌊log2𝑛⌋−1)H(h1=1,h2=3,h3=7,…,h⌊log2n⌋=2⌊log2n⌋−1) Shell-Sort 执行顺序为：InsertionSort(ℎ⌊log2𝑛⌋),InsertionSort(ℎ⌊log2𝑛⌋−1),…,InsertionSort(ℎ2),InsertionSort(ℎ1)InsertionSort(h⌊log2n⌋),InsertionSort(h⌊log2n⌋−1),…,InsertionSort(h2),InsertionSort(h1)． 以下设 𝑛 ≥4n≥4，分两部分去分析复杂度： 对于前面的若干个满足 ℎ𝑡 ≥√𝑛ht≥n 的 ℎ𝑡ht，显然有 InsertionSort(ℎ𝑡)InsertionSort(ht) 的时间复杂度为 𝑂(𝑛2ℎ𝑡)O(n2ht)． 取 𝑘 =min{𝑡 :ℎ𝑡 ≥√𝑛}k=min{t:ht≥n}，则 ℎ𝑘 =Θ(√𝑛)hk=Θ(n)，有： 𝑂(𝑛2ℎ𝑘)=𝑂(𝑛3/2)O(n2hk)=O(n3/2) 而对于 𝑖 >𝑘i>k 的 ℎ𝑖hi，因为有 2ℎ𝑖 <ℎ𝑖+12hi 𝑂(𝑛2ℎ𝑖)=𝑂(𝑛3/2/2𝑖−𝑘)(𝑖>𝑘)O(n2hi)=O(n3/2/2i−k)(i>k) 所以大于等于 √𝑛n 部分的总时间复杂度为： ⌊log2𝑛⌋∑𝑖=𝑘𝑂(𝑛3/2/2𝑖−𝑘)=𝑂(𝑛3/2)∑i=k⌊log2n⌋O(n3/2/2i−k)=O(n3/2)对于后面剩下的满足 ℎ𝑡 <√𝑛ht 𝑂(𝑛ℎ𝑡+2ℎ𝑡+1ℎ𝑡)=𝑂(𝑛ℎ𝑡+2⋅ℎ𝑡+2/2ℎ𝑡+2/4)=𝑂(𝑛ℎ𝑡+2)O(nht+2ht+1ht)=O(nht+2⋅ht+2/2ht+2/4)=O(nht+2) 再次利用 2ℎ𝑖 <ℎ𝑖+12hi 2𝑂(𝑛3/2)+𝑘−3∑𝑖=1𝑂(𝑛ℎ𝑖+1)=𝑂(𝑛3/2)+𝑘−3∑𝑖=1𝑂(𝑛ℎ𝑘−1/2𝑘−𝑖−3)=𝑂(𝑛3/2)+𝑂(𝑛ℎ𝑘−1)=𝑂(𝑛3/2)2O(n3/2)+∑i=1k−3O(nhi+1)=O(n3/2)+∑i=1k−3O(nhk−1/2k−i−3)=O(n3/2)+O(nhk−1)=O(n3/2) 综上可得总时间复杂度即为 𝑂(𝑛3/2)O(n3/2)． 命题 2 证明 注意到一个事实：如果已经执行过了 InsertionSort(2)InsertionSort(2) 与 InsertionSort(3)InsertionSort(3)，那么因为 2 ⋅3 −2 −3 =12⋅3−2−3=1，所以由定理 22，每个元素只有与它相邻的前一个元素可能大于它，之前的元素全部都不大于它．于是 𝑖i 指针只需要最多两次就可以退出 while 循环．也就是说，此时再执行 InsertionSort(1)InsertionSort(1)，复杂度降为 𝑂(𝑛)O(n)． 更进一步：如果已经执行过了 InsertionSort(4)InsertionSort(4) 与 InsertionSort(6)InsertionSort(6)，我们考虑所有的下标为奇数的元素组成的子列与下标为偶数的元素组成的子列．则这相当于把这两个子列分别执行 InsertionSort(2)InsertionSort(2) 与 InsertionSort(3)InsertionSort(3)．那么也是一样，这时候再执行 InsertionSort(2)InsertionSort(2)，相当于对两个子列分别执行 InsertionSort(1)InsertionSort(1)，也只需要两个序列和的级别，即 𝑂(𝑛)O(n) 的复杂度就可以将数组变为 22 间隔有序． 不断归纳，就可以得到：如果已经执行过了 InsertionSort(2ℎ)InsertionSort(2h) 与 InsertionSort(3ℎ)InsertionSort(3h)，则执行 InsertionSort(ℎ)InsertionSort(h) 的复杂度也只有 𝑂(𝑛)O(n)． 接下来分为两部分分析复杂度： 对于 ℎ𝑡 >𝑛/3ht>n/3 的部分，则执行每个 InsertionSort(ℎ𝑡)InsertionSort(ht) 的复杂度为 𝑂(𝑛2/ℎ𝑡)O(n2/ht)． 而 𝑛2/ℎ𝑡 <3𝑛n2/ht<3n，所以单次插入排序复杂度为 𝑂(𝑛)O(n)． 而这一部分元素个数是 𝑂(log2𝑛)O(log2n) 级别的，所以这一部分时间复杂度为 𝑂(𝑛log2𝑛)O(nlog2n)． 对于 ℎ𝑡 ≤𝑛/3ht≤n/3 的部分，因为 3ℎ𝑡 ≤𝑛3ht≤n，所以这之前已经执行了 InsertionSort(2ℎ𝑡)InsertionSort(2ht) 与 InsertionSort(3ℎ𝑡)InsertionSort(3ht)，于是执行 InsertionSort(ℎ𝑡)InsertionSort(ht) 的时间复杂度是 𝑂(𝑛)O(n)． 还是一样的，这一部分元素个数也是 𝑂(log2𝑛)O(log2n) 级别的，所以这一部分时间复杂度为 𝑂(𝑛log2𝑛)O(nlog2n)． 综上可得总时间复杂度即为 𝑂(𝑛log2𝑛)O(nlog2n)． 空间复杂度希尔排序的空间复杂度为 𝑂(1)O(1)． 实现C++1Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15template 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; } } 1 2 3 4 5 6 7 8 9 10 11def 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) 参考资料与注释希尔排序 - 维基百科，自由的百科全书 ↩ 本页面最近更新：2026/11/4 20:10:15，更新历史发现错误？想一起完善？ 在 GitHub 上编辑此页！本页面贡献者：Tiphereth-A, NachtgeistW, iamtwz, Alisahhh, c-forrest, CroMarmot, Enter-tainer, HeRaNO, lailai0916, Menci, partychicken, Peanut-Tang, shawlleyw, ShwStone, Xeonacid本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用