想象你是一个图书管理员，面前有一排 1000 本乱序的书。若按普通方式一本本相邻比较整理，就像蜗牛爬，一次只能挪动一格；书若错得远，就要来回搬很多趟。聪明的做法是：先每隔 5 本抽一组快速粗排，让整排书大致有序；再缩小到每隔 3 本抽一组；最后每隔 1 本从头到尾细排。粗排几轮后，最后细排的搬动就少得多了。这个「先大步粗调，再小步细调」的思路，就是希尔排序的核心。你需要的不是一种固定的跳法，而是一整套「间隔方案」——也就是增量序列（Gap 序列）。本文将带你看看不同的跳法（Shell、Hibbard、Sedgewick）如何影响整理速度，以及它们各自适合什么样的书架。

岗位关联

一句话价值：对 AI 从业者而言，理解增量序列设计能帮你评估算法性能、在工程中合理选择排序方案，也是面试中展示算法功底的高频考点。

目录
  1. 可视化演示
  2. 增量分组策略
  3. Shell增量序列
  4. Hibbard增量序列
  5. Sedgewick增量序列
  6. Gap序列影响
  7. 与插入排序对比
  8. 实验测试数据
  9. 实用价值场景
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

希尔排序是插入排序的改进版本，通过增量分组逐步缩小间隔实现更高效的排序。本文讲解希尔排序的增量序列设计与分组策... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

希尔排序基本：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

增量分组策略

想象图书管理员小李面对 1000 本乱书。他意识到，与其让书一本本贴着相邻位置挪动，不如先「隔几本抽一组」：比如从第 1 本开始，每隔 4 本取出 1 本，组成一组，快速把这组排好；再换一个起点，抽出另一组……几轮之后，整排书虽然还没完全有序，但已经「大体有序」。这种先粗排再细排的策略，正是希尔排序的灵魂。

在算法中，「隔几本」这个间隔被称为 gap，也叫增量 h。每一轮，数组按间隔 h 被拆成 h 个互不相交的子序列；每个子序列内部做一次插入排序。一轮完成后，把 h 缩小，重复上面的分组排序。当 h 从 4 减到 2、再到 1，最后一次 h=1 时，整个数组就是一个子序列，直接做普通插入排序。因为前面几轮已经消除了大量远距离错位，最后一轮的插入排序需要移动的元素很少，所以很快。

用数学语言描述，第 k 轮的子序列可以写成下面的集合。这里 A 是待排序数组，h 是当前增量，i 是该组第一个元素的起始下标，从 0 到 h-1 一共 h 组：

你看，小李不需要一开始就精排每一本书。先分组粗排，让书以「跳跃式」接近最终位置，最后再细细检查一遍。这个「大跨步、小收敛」的节奏，就是希尔排序最核心的分组策略。

Gi={A[i], A[i+h], A[i+2h], A[i+3h], … },i=0,1,…,h−1G_i = \{A[i],\, A[i+h],\, A[i+2h],\, A[i+3h],\, \dots\}, \quad i=0,1,\dots,h-1
通俗说明：这个公式把一排书按「相同跨步」拆成 h 摞，每摞内部按插入排序整理。
  1. 数组 AA 存放所有待排序元素，A[i] 表示下标为 i 的那本书的价值。
    A[i],i=0,1,…,n−1A[i],\quad i=0,1,\dots,n-1
  2. 增量 h当前轮次的间隔步长，h 越大，抽书的跨度越大。
    h∈{h1,h2,…,ht},ht=1h \in \{h_1, h_2, \dots, h_t\}, \quad h_t = 1
  3. 子序列 G_i从起始下标 i 出发，每跳 h 步取一个元素，直到越过数组末尾。
    Gi={A[i+mh]∣m=0,1,2,… }G_i = \{A[i + mh] \mid m = 0,1,2,\dots \}
  4. 组数因为 i 取值 0 到 h-1，恰好构成 h 组，覆盖所有下标。
    ∣{Gi}∣=h|\{G_i\}| = h

Shell增量序列

小李最初想到的跳法很简单：书架有 1000 本，先每隔 500 本抽一组，再每隔 250 本，再 125……也就是每次把间隔砍半。这个直觉方案，就是计算机科学家 Shell 在 1959 年提出希尔排序时采用的增量序列，也是教科书里最常见的入门写法。

Shell 增量的递推规则是：先把数组长度 n 除以 2 作为第一轮 gap，之后每一轮都取上一轮 gap 的一半，向下取整，直到 gap 变为 1。例如 n=10 时，gap 依次为 5、2、1；n=16 时为 8、4、2、1。它的实现非常朴素，几乎不需要额外计算增量序列，所以在原型验证中经常出现。

写成公式就是：

不过小李很快发现，一味折半虽然省脑子，但有些书还是要来回搬很多趟。原因在于不同轮次的 gap 之间可能有公因数，导致之前的粗排「白做」了一部分。于是，更聪明的跳法开始登场。

h0=⌊n2⌋,ht+1=⌊ht2⌋,ht>0h_0 = \left\lfloor \frac{n}{2} \right\rfloor, \qquad h_{t+1} = \left\lfloor \frac{h_t}{2} \right\rfloor, \quad h_t > 0
通俗说明：每一轮步长都严格减半，最终必达 1，保证最后一轮是完整插入排序。
  1. 初始增量h0 取 n/2 的整数部分，比如 10 本书先从间隔 5 开始。
    h0=⌊n/2⌋h_0 = \lfloor n/2 \rfloor
  2. 递推关系下一轮增量是上一轮的一半，遇到奇数时向下取整。
    ht+1=⌊ht/2⌋h_{t+1} = \lfloor h_t / 2 \rfloor
  3. 终止条件只要 h_t 大于 0 就继续，最终必然出现 h=1。
    ht=1(t=tmax⁡)h_t = 1 \quad (t = t_{\max})

Hibbard增量序列

小李去请教有经验的老管理员，对方说「别总折半，试试 1、3、7、15……这样的间隔」。这些数字都是 2 的幂减 1，彼此之间几乎没有公因数，相当于每次粗排都换一种「跨度组合」，让书可以在不同尺度上快速归位。

这是 Hibbard 在 1963 年提出的增量序列。第 k 项是 2^k − 1，使用时从大到小选取。例如 n=100 时，可取 63、31、15、7、3、1。由于相邻轮次的间隔互质，排序时不会像 Shell 增量那样出现大量重复的「原地踏步」，最坏复杂度被降到了 O(n^{3/2})，明显优于 Shell 增量的 O(n²)。

Hibbard 的秘诀是让不同轮次「用力方向」不重叠，就像小李每次换一种跳格子方式，避免同一批书反复被折腾。不过，工程师们还不满足，他们想要更快。

hk=2k−1,k=1,2,3,…h_k = 2^k - 1, \qquad k = 1, 2, 3, \dots
通俗说明：从 k=1 开始生成 1，3，7，15……实际使用时按从大到小的顺序逐轮应用。
  1. 序号 k从 1 开始计数，每个 k 对应一个增量候选。
    k∈{1,2,3,… }k \in \{1,2,3,\dots\}
  2. 通项公式第 k 项 = 2 的 k 次方减 1，k 越大增量越大。
    hk=2k−1h_k = 2^k - 1
  3. 逆序使用为了让增量从大到小递减，先选出小于 n 的最大项，再逐步减小。
    ht<n,且从大到小排列h_t < n, \quad \text{且从大到小排列}

Sedgewick增量序列

小李后来遇到一位数据狂人，对方拿出一个更花哨的跳法表：1、5、19、41、109、209……这些数字由两套公式交替生成，既有大跨步打散，又有小跨步微调，像一套精心编排的「交叉训练计划」。

这就是 Sedgewick 增量序列，它是工程中最常用的序列之一。实践中它把最坏时间复杂度压到了约 O(n^{4/3})（经验值），进一步缩小了与 O(n log n) 算法的差距。它的构造方式是把两个子序列交错合并，形成覆盖更全面的间隔集合。

Sedgewick 的精妙之处在于，它把「大尺度」和「小尺度」两套跳法揉在一起，既不像 Shell 那样偷懒，也不像 Hibbard 那样单调。小李在书架上试了试，明显感觉搬运次数更少了。

hk=9⋅4k−9⋅2k+1,hk′=4k−3⋅2k+1h_k = 9\cdot 4^k - 9\cdot 2^k + 1, \qquad h'_k = 4^k - 3\cdot 2^k + 1
通俗说明：两个公式分别生成 1、19、109、…… 和 1、5、41、209…… 再交替排序，得到完整序列。
  1. 第一个子序列k 从 0 开始，代入得到 1、19、109、505……
    9⋅4k−9⋅2k+19\cdot 4^k - 9\cdot 2^k + 1
  2. 第二个子序列同样代入 k=0,1,2…… 得到 1、5、41、209……
    4k−3⋅2k+14^k - 3\cdot 2^k + 1
  3. 合并策略将两个子序列按升序合并，并去掉重复的 1，得到最终序列。
    {1,5,19,41,109,209,… }\{1,5,19,41,109,209,\dots\}
  4. 使用方式与 Hibbard 一样，按从大到小依次作为 gap，最后一轮 h=1。

Gap序列影响

小李现在明白了，gap 序列就是「整理书架的策略表」。同样 1000 本书，用不同的策略表，搬书总次数可以相差一个数量级。也就是说，gap 的选择直接决定希尔排序的命脉。

增量序列之所以影响巨大，是因为它决定了每个元素在每轮能跨多远、要比较多少次。增量太小，元素移动慢；增量太大，组内元素太少，粗排效果有限。更重要的是，若相邻轮次间隔不互质，后面几轮可能重复处理已经有序的范围，浪费比较和移动。

综合前面的分析，不同增量的最坏复杂度可汇总为：

所以，选对策略表，就能像小李一样用最少的搬书次数让书架整齐；选错，就只能像蜗牛一样在一堆书里爬来爬去。

TShell(n)=O(n2),THibbard(n)=O(n32),TSedgewick(n)≈O(n43)T_{\text{Shell}}(n) = O(n^2), \quad T_{\text{Hibbard}}(n) = O(n^{\frac{3}{2}}), \quad T_{\text{Sedgewick}}(n) \approx O(n^{\frac{4}{3}})
通俗说明：指数越小，理论上最坏情况下需要操作的次数越少。
  1. 复杂度记号 O描述当 n 增大时，操作次数增长速度的上界。
    O(f(n))O(f(n))
  2. Shell 增量最坏仍是平方级，n 大十倍，最坏操作约百倍。
    O(n2)O(n^2)
  3. Hibbard 增量指数 3/2，介于 n 和 n² 之间。
    O(n3/2)O(n^{3/2})
  4. Sedgewick 增量经验复杂度指数 4/3，实际表现更好。
    O(n4/3)O(n^{4/3})

与插入排序对比

把普通插入排序想象成只允许「左右相邻」移动的管理员，而希尔排序则可以「隔空投递」。当书从书架一端跑到另一端时，前者要一步一步蹭过去，后者几步就能跨越半个书架。

插入排序每轮只比较相邻元素，一次只能消除一个逆序对；希尔排序通过增量分组，让一个元素在单轮中跨越多个位置，一次就能消除大量逆序对。因此，数据规模增大时，两者的耗时差距迅速拉大。但当 n 很小或数组近乎有序时，插入排序的常数更小，希尔排序的预排序反而成了负担。

小李总结：短书架用蜗牛没问题，中等书架蜗牛会累趴，而隔空投递加细查的希尔排序，正好是那个聪明的折中方案。

TInsertion(n)=O(n2),TShell(n)=O(n43)(empirical)T_{\text{Insertion}}(n) = O(n^2), \qquad T_{\text{Shell}}(n) = O(n^{\frac{4}{3}}) \quad \text{(empirical)}
通俗说明：当 n 从 1000 涨到 10000，插入排序最坏操作约增大 100 倍，而希尔排序约增大 21 倍左右。
  1. 插入排序复杂度最坏和平均都是平方级，n 越大增长越可怕。
    TInsertion(n)=O(n2)T_{\text{Insertion}}(n) = O(n^2)
  2. 希尔排序经验复杂度指数 4/3 小于 2，所以增长更平缓。
    TShell(n)=O(n4/3)T_{\text{Shell}}(n) = O(n^{4/3})
  3. 实际分界当 n 小于某个阈值时，插入排序反而更快。
    n≤nc⇒TInsertion<TShelln \le n_c \Rightarrow T_{\text{Insertion}} < T_{\text{Shell}}

实验测试数据

口说无凭，小李在三个不同大小的书架上做了实验，给每种跳法都配了一个「计步器」。数据告诉他，策略表的差异在书架变大后有多么残酷。

实验中分别对 n=1000、10000、100000 的随机数组，使用三种增量序列排序。结果发现：n=1000 时三者差距很小；n=10000 时 Shell 耗时约为 Hibbard 的 1.3 倍；n=100000 时，Sedgewick 明显领先，Shell 已显吃力。这说明增量序列的收益会随着数据规模放大而放大。

用复杂度模型可以估算规模翻倍后的耗时。假设希尔排序耗时 T(n) ≈ c·n^{4/3}，则规模翻倍时耗时比例是：

计步器上的数字让小李彻底信服：越是书架变大，最初多花心思设计跳法就越值得。这就是 gap 优化带来的实打实收益。

T(2n)T(n)≈243≈2.52\frac{T(2n)}{T(n)} \approx 2^{\frac{4}{3}} \approx 2.52
通俗说明：数据翻一倍，时间大约变成原来的 2.5 倍，而不是插入排序的 4 倍。
  1. 相除规模变为 2n 与规模 n 的耗时之比。
    T(2n)T(n)\frac{T(2n)}{T(n)}
  2. 代入模型T(n) 与 n^{4/3} 成正比，所以变成 (2n)^{4/3} / n^{4/3}。
    =(2nn)43=243= \left(\frac{2n}{n}\right)^{\frac{4}{3}} = 2^{\frac{4}{3}}
  3. 数值约算2 的 4/3 次方约为 2.52。
    243≈2.522^{\frac{4}{3}} \approx 2.52

实用价值场景

小李的书架中等大小、位置固定、还不能占用太多临时空间，这时他不需要大型自动分拣机器人，只需要一个不占地方的便携工具箱——希尔排序正是这样一个工具箱。

希尔排序只需要一个临时变量做交换辅助，不需要额外的大块内存，因此空间复杂度是 O(1)。在嵌入式设备、内存受限系统等场景中，这是一个非常宝贵的性质。当数据规模在十万级以内时，它比插入排序快得多，实现起来又比快排、归并简单，非常适合中小规模的排序任务。

当数据规模超过百万级，小李就会把书架交给更专业的快排或归并排序；但在这之前，这个不占地方的希尔排序，依然是性价比极高的选择。理解它的 Gap 优化，也就理解了「先粗后细」的算法智慧。

S(n)=O(1)S(n) = O(1)
通俗说明：不管排多少本书，除了数组本身，额外只需要少量固定空间，不会随着规模增长而膨胀。
  1. 空间复杂度 S(n)衡量排序过程中除了输入数组外，额外使用的存储空间。
    S(n)S(n)
  2. 常数级 O(1)额外空间不随 n 增长，始终是常量级。
    S(n)=O(1)S(n) = O(1)
  3. 工程含义适合内存紧张或对递归栈深度敏感的环境。
    in-place,no recursion\text{in-place}, \quad \text{no recursion}

AI 应用场景

嵌入式传感器数据排序

阶段：数据预处理

解决的问题：微型传感器节点内存极小，排序数据量在几万以内。插入排序太慢，快速排序又需要递归栈空间，正好需要一种原地、实现简单、中等规模高效的排序算法。

具体案例：智能农业中的土壤传感节点每天收集 8000 条温度数据后排序上传。采用 Sedgewick 增量序列的希尔排序，在几十毫秒内完成排序，且不额外占用内存，电池续航明显改善。

排行榜实时粗排序

阶段：在线特征计算与榜单生成

解决的问题：游戏或推荐系统需要频繁维护中等规模的分数列表，要求低延迟和稳定内存占用。若每次用插入排序维护，数据波动大时会很慢；用快排又担心递归开销。

具体案例：直播平台实时贡献榜有 2 万在线用户，每分钟重排一次。先用希尔排序做一次基础粗排，之后只对增量变化做插入排序微调，整体耗时比纯插入排序减少约 60%。

算法原型验证中的快速排序

阶段：模型选型与原型验证

解决的问题：在跑通流程阶段，不想引入复杂排序库，需要快速实现、易调试、行为可预测的排序方法。希尔排序代码量小，且 Gap 序列可配置，适合作为占位实现。

具体案例：NLP pipeline 里对 5000 个候选词按置信度排序，先用希尔排序跑通整体流程，后期再替换为更优化的 Timsort。这样既不影响原型迭代，又能观察不同 Gap 序列对排序耗时的影响。

Python 演示

python70 行
# -*- coding: utf-8 -*-"""希尔排序与增量序列对比"""import random  def insert_by_gap(arr, gap, start, stat):    for i in range(start + gap, len(arr), gap):        temp = arr[i]        j = i - gap        while j >= start and arr[j] > temp:            stat["cmp"] += 1            arr[j + gap] = arr[j]            stat["mov"] += 1            j -= gap        arr[j + gap] = temp  def shell_sort(arr, gaps):    stat = {"cmp": 0, "mov": 0}    for gap in gaps:        for start in range(gap):            insert_by_gap(arr, gap, start, stat)    return stat  def shell_gaps(n):    gaps = []    h = n // 2    while h > 0:        gaps.append(h)        h //= 2    return gaps  def hibbard_gaps(n):    gaps = []    k = 1    while True:        h = (1 << k) - 1        if h >= n:            break        gaps.append(h)        k += 1    return gaps[::-1]  def sedgewick_gaps(n):    seq = [1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905]    return [h for h in seq if h < n][::-1]  def main():    n = 5000    data = [random.randint(0, 99999) for _ in range(n)]    gap_funcs = [        ("Shell", shell_gaps),        ("Hibbard", hibbard_gaps),        ("Sedgewick", sedgewick_gaps),    ]    for name, func in gap_funcs:        arr = data[:]        gaps = func(n)        stat = shell_sort(arr, gaps)        ok = arr == sorted(data)        print("%-8s gaps=%-20s cmp=%d mov=%d ok=%s" %              (name, str(gaps[:6]) + "...", stat["cmp"], stat["mov"], ok))  if __name__ == "__main__":    main()
目的：用同一份随机数组对比 Shell、Hibbard、Sedgewick 三种增量序列的比较次数和移动次数，直观看到 Gap 优化的差异。
  1. for i in range(start + gap, len(arr), gap):从 gap 后的元素开始，以 gap 为步长遍历子序列，对应「每组只排自己的书」。
  2. while j >= start and arr[j] > temp:把大数往后搬，条件从相邻变为跨 gap，体现希尔排序能远距离移动。
  3. stat["cmp"] += 1记录比较次数，用于后续对比增量序列的好坏。
  4. for gap in gaps:逐轮应用增量序列，体现 gap 递减策略。
  5. h //= 2Shell 增量每次折半，得到最朴素的间隔方案。
  6. (1 << k) - 1用移位计算 2^k − 1，生成 Hibbard 增量序列。
  7. [h for h in seq if h < n][::-1]过滤并倒序，得到从大到小的 Sedgewick 增量序列。
  8. arr = data[:]复制数组，保证每个增量序列排的是同一份原始数据。
  9. ok = arr == sorted(data)验证本轮排序是否正确。

常见误区

误区希尔排序不就是插入排序的改进吗？插入排序是稳定的，所以希尔排序应该也是稳定的。

正解插入排序稳定是因为它只在相邻位置做交换，相同元素不会越过对方。希尔排序的分组会让元素跨很大的间隔跳来跳去，这在过程中完全可能改变相同元素的相对顺序，所以它是典型的不稳定排序。就像整理书架时，两本同名书可能被不同轮次的抽排打乱相对位置。

为何常见：学习者容易把「改进版本」自动等同于「继承所有性质」，忽略了跨距离移动这个关键差异。

误区反正最后一轮都是插入排序，gap 怎么选问题都不大，能到 1 就行。

正解gap 序列直接决定希尔排序的复杂度上界。Shell 增量最坏 O(n²)，Hibbard 能到 O(n^{3/2})，Sedgewick 经验约 O(n^{4/3})。如果 gap 选择不当，希尔排序可能退化成插入排序的龟速。就像跳格子方法不好，会在书堆里来回绕路。

为何常见：初学时只用一种固定 gap 跑通代码，没有对比过不同序列的性能，容易低估 gap 设计的重要性。

误区很多教材默认写 h=n/2 每次折半，所以这就是希尔排序的标准最优增量。

正解n/2 折半只是 Shell 原始论文中的初始建议，并非最优。Hibbard、Sedgewick 等序列在理论和实验上都更优。工程中常用 Sedgewick 等序列提升性能。教材选 n/2 只是为了代码简单。

为何常见：教材例题为了便于演示，往往展示最简单的 n/2，读者会误以为这是唯一且最优的增量选择。

误区希尔排序是插入排序的升级，任何规模下都应该更快。

正解当 n 很小（比如 10 个以内）或数组已经近乎有序时，插入排序的常数开销更小，反而更快。希尔排序的预排序阶段会带来额外比较，在小规模下不划算。工程中 Timsort 等混合排序会针对小规模切换到插入排序。

为何常见：人们习惯用「复杂度类别」直接判断所有规模，忽略了常数因子和实际数据特点。

面试题

Q1. 希尔排序是对哪种排序算法的改进？

单选题 · easy

  • A.冒泡排序
  • B.插入排序← 正确答案
  • C.选择排序
  • D.归并排序

答案：B。希尔排序通过增量分组让元素跨距离移动，本质还是插入排序在多个子序列上的应用，所以它是插入排序的改进版本。A、C、D 与此无关。

Q2. 在使用 Shell 增量序列时，下一轮 gap 通常取上一轮的多少？

单选题 · easy

  • A.一半（向下取整）← 正确答案
  • B.三分之一
  • C.固定减一
  • D.两倍

答案：A。Shell 增量的规则是 n/2 向下取整，随后逐轮折半直到 1。因此选 A。B、C、D 都不是 Shell 增量的定义。

Q3. 希尔排序最后一轮的 gap 必须是？

单选题 · easy

  • A.0
  • B.1← 正确答案
  • C.2
  • D.n

答案：B。gap=1 时所有元素在同一组，等同于普通插入排序，这是保证数组完全有序的必要条件。gap 为 0、2、n 都无法完成完整的全量插入排序。

Q4. Hibbard 增量序列 h_k 的公式是？

单选题 · mid

  • A.2^k − 1← 正确答案
  • B.2^k + 1
  • C.4^k − 1
  • D.n / 2^k

答案：A。Hibbard 序列是 1, 3, 7, 15……，由 2^k − 1 生成，不同增量间互质，最坏复杂度 O(n^{3/2})。B、C、D 均不符合定义。

Q5. Shell 增量序列的希尔排序最坏时间复杂度是？

单选题 · mid

  • A.O(n log n)
  • B.O(n²)← 正确答案
  • C.O(n^{3/2})
  • D.O(n)

答案：B。Shell 增量虽然做了分组预排序，但最坏仍可能退化为平方级，即 O(n²)。Hibbard 才能达到 O(n^{3/2})，Sedgewick 经验约 O(n^{4/3})。

Q6. 关于希尔排序的稳定性，下列说法正确的是？

单选题 · mid

  • A.稳定排序
  • B.不稳定排序← 正确答案
  • C.数据有序时稳定
  • D.与插入排序一样稳定

答案：B。插入排序稳定是因为相邻交换，而希尔排序会跨距离移动元素，相同值的相对顺序可能被改变，所以它是不稳定排序。A、C、D 都不成立。

Q7. 以下哪些是希尔排序的特点？

多选题 · mid

  • A.原地排序，空间复杂度 O(1)← 正确答案
  • B.不稳定的排序方法← 正确答案
  • C.任何规模都比插入排序快
  • D.最后会退化为普通插入排序完成排序← 正确答案

答案：ABD。希尔排序只使用常数级辅助空间，且不稳定；当 gap=1 时确实退化为普通插入排序。C 错，因为 n 很小或近乎有序时插入排序可能更快。

Q8. 关于增量序列对希尔排序的影响，下列说法正确的有？

多选题 · mid

  • A.增量必须最终递减到 1← 正确答案
  • B.相邻轮次的间隔互质一般会带来更好效果← 正确答案
  • C.增量序列越短越好
  • D.不同增量序列会导致不同时间复杂度← 正确答案

答案：ABD。gap=1 是保证正确性的必要条件；互质间隔能减少重复劳动；不同增量序列复杂度从 O(n²) 到 O(n^{4/3}) 不等。C 错，增量太短可能起不到粗排效果。

Q9. 与普通插入排序相比，希尔排序能够在中等规模数据上更快的原因是？

多选题 · hard

  • A.一次移动可以跨越多个位置← 正确答案
  • B.更早消除远距离逆序对← 正确答案
  • C.对所有数据都更稳定
  • D.通过减少后续插入排序的比较和移动次数← 正确答案

答案：ABD。希尔排序的核心优势是跨距离移动和提前消除逆序对，这让最后一轮插入排序非常轻松。C 说的是稳定性，与提速无关，且希尔排序本身不稳定。

Q10. 某数组规模扩大一倍，用经验复杂度 O(n^{4/3}) 估算，希尔排序耗时约为原来的多少倍？

单选题 · hard

  • A.1.5
  • B.2.0
  • C.2.52← 正确答案
  • D.4.0

答案：C。根据 T(n) ≈ c·n^{4/3}，规模翻倍后耗时比约为 2^{4/3} ≈ 2.52，因此选 C。A、B 偏小，D 是插入排序规模翻倍的近似增长。