难度：进阶。题目原型为 AOJ ALDS1_2_D Shell Sort。本题考察的是希尔排序的增量序列与交换次数统计：把插入排序按间隔分组，用「3g+1」增量序列保证在大数据量下仍可接受。

目标

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

• 解释希尔排序为什么比普通插入排序快：先在粗间隔上把元素大致归位，再逐步细化；
• 按 3g+1（1, 4, 13, 40, …）生成增量序列，并倒序使用；
• 在对每个 gap 做插入排序时，正确统计元素后移（交换）的次数；
• 理解为什么交换次数需要用 long long。

前置知识

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

题目

给一个长度为 n 的整数序列 a，用希尔排序把它从小到大排好。增量序列取 3g+1（即 1, 4, 13, 40, 121, …），使用时按从大到小的顺序，从「不超过 n 的最大 gap」开始。排序过程中，每当元素在插入时向后移动一次，交换次数加 1。

输入格式

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

输出格式

• 第一行一个整数 m，表示使用的 gap 数量；
• 第二行 m 个整数，即使用的 gap，按降序用空格分隔；
• 第三行一个整数，表示交换次数；
• 接下来 n 行，每行一个整数，依次输出排序后的序列。

数据范围

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

样例

样例输入

5
5 1 4 3 2

样例输出

2
4 1
3
1
2
3
4
5

样例解释

n = 5 时增量序列取 1, 4（13 > 5 故舍去），倒序使用即 [4, 1]，共 m = 2 个。gap 为 4 时发生 1 次交换，gap 为 1 时发生 2 次交换，共 3 次，排序结果为 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-13-shell-sort-count
pnpm lab:score -- labs/chapter-10/exercise/E-10-13-shell-sort-count

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

完成清单

• 样例输出与题目一致
• 升序、降序、含重复值三种情况都通过
• 能说出增量序列 3g+1 为什么要在不超 n 的前提下取到最大，并倒序使用

思考题

1. 如果直接把增量序列固定为 n/2, n/4, …, 1，为什么最坏情况下会退化到 O(n²)？3g+1 序列避免了什么问题？
2. 交换次数统计的是「元素后移」的次数，它和冒泡排序的「相邻交换」次数含义相同吗？

题解

点击查看题解

思路

希尔排序是「分组插入排序」：

1. 生成增量序列 g = 1, 4, 13, …（g = 3g + 1），只保留不超过 n 的值，再倒序使用；
2. 对每个 g，把下标模 g 相同的元素看成一列，做一次间隔为 g 的插入排序；
3. 插入时若前一个间隔元素更大，就把它后移 g 位，交换次数加 1。

外层循环生成 gap，内层就是对「每个间隔子序列」做插入排序，逻辑与普通插入排序几乎一致，只是步长从 1 变成 g。

复杂度分析

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