难度：进阶。题目原型为洛谷 P9206（私题，题面自定）。本题考察的是希尔排序的标准写法：用 3g+1 增量序列把序列从小到大排好，作为希尔排序的模板题。

目标

完成本题后，你应该能够：

• 手写出「间隔为 g 的插入排序」内层循环；
• 用 3g+1 生成增量序列并按从小到大顺序逐层排序；
• 理解希尔排序与普通插入排序的区别：把步长 1 替换成可变的 gap。

前置知识

• 10.1 插入排序的基本过程；
• 增量序列（gap）的概念。

题目

给一个长度为 n 的整数序列 a，用希尔排序（增量序列 3g+1）把它从小到大排序，并把结果输出到一行。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数，表示序列 a。

输出格式

一行 n 个整数，表示从小到大排序后的序列，相邻整数用一个空格分隔。

数据范围

项目	范围
序列长度 n	1 ≤ n ≤ 10⁵
元素值	−10⁹ ≤ a[i] ≤ 10⁹

样例

样例输入

5
5 1 4 3 2

样例输出

1 2 3 4 5

样例解释

用 3g+1 增量序列（1, 4, …）做希尔排序后，序列变为升序 1 2 3 4 5。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-10/exercise/E-10-14-shell-sort-xufu
pnpm lab:score -- labs/chapter-10/exercise/E-10-14-shell-sort-xufu

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 升序、降序、含重复值、含负数四种情况都通过
• 能说出内层 while 循环的退出条件为什么是 j >= 0 && a[j] > v

思考题

1. 希尔排序的内层循环和普通插入排序几乎一样，唯一区别在哪里？为什么改一个步长就能变快？
2. 如果增量序列里包含较大的 gap，先按大 gap 排序有什么意义？

题解

点击查看题解

思路

希尔排序按「从粗到细」的间隔对序列做插入排序：

1. 生成增量序列 g = 1, 4, 13, …（g = 3g + 1），只保留不超过 n 的值；
2. 对每个 g，从下标 g 开始，把 a[i] 插入到「步长为 g」的有序前缀中；
3. 内层 while (j >= 0 && a[j] > v) 把更大的元素逐个后移 g 位，最后把 v 放回空位。

全部 gap 处理完后序列有序。

复杂度分析

• 时间复杂度：增量序列为 3g+1 时约为 O(n^1.3)；
• 空间复杂度：O(1) 额外空间（忽略输入数组本身）。