希尔排序
希尔排序（Shell Sort）是插入排序的改进版，也称“缩小增量排序”。其基本思想是：先将整个序列按一定增量分组，对每组分别进行插入排序，然后逐步缩小增量，最终整体插入排序。
点击“执行一步”观察算法状态变化。
- 选定一个初始增量 ，将序列分为若干组
- 对每组分别进行插入排序
- 缩小增量 ，重复分组和排序
- 当 时，整体插入排序，排序完成
伪代码如下：
for gap = n/2; gap >= 1; gap = gap/2:
for i = gap to n-1:
key = A[i]
j = i - gap
while j >= 0 and A[j] > key:
A[j+gap] = A[j]
j = j - gap
A[j+gap] = keyvoid ShellSort(int A[], int n) {
// 增量序列：n/2, n/4, ..., 1（可换用 Hibbard 等更优序列）
for (int gap = n / 2; gap >= 1; gap /= 2) {
// 对每个分组进行直接插入排序
for (int i = gap; i < n; i++) {
int key = A[i];
int j = i - gap;
while (j >= 0 && A[j] > key) {
A[j + gap] = A[j]; // 组内元素后移 gap 位
j -= gap;
}
A[j + gap] = key;
}
}
}增量序列的选择
- 常用序列：（简单但最坏 ）
- Hibbard 序列：，最坏
- Sedgewick 序列：，性能更好
增量序列的选择直接影响希尔排序的效率，是研究重点。
- 最好情况：
- 最坏情况：（与增量序列有关）
- 空间复杂度：
- 稳定性：不稳定排序
习题 1
简述希尔排序的基本思想及其与直接插入排序的区别。
解题思路：
本题考查希尔排序的基本思想及其与直接插入排序的区别。区别在于插入的对象不是单个相邻元素，而是“间距为增量”的同组元素；随着增量逐趟缩小，分组越来越细，最终退化为一次普通的直接插入排序。
详细步骤：
- 希尔排序先分组插入，逐步缩小增量
- 直接插入每次只插入一个元素
- 补充说明：同一组内的元素间距为增量 ，先对每个分组各做一次直接插入排序；增量逐趟减半直至为 1 时，各组就退化为相邻元素，整体相当于一次直接插入排序，但此时序列已接近有序，所需移动次数大幅减少。
最终答案：
希尔排序分组插入，效率高于直接插入。
习题 2
希尔排序的时间复杂度和空间复杂度分别是多少？
解题思路：
本题考查希尔排序的复杂度分析。希尔排序的效率取决于增量序列的选择：增量取得好时最好情况可达 ，而若序列本身已有序则每次比较都要发生交换，退化为最坏的 ；排序只在原数组内进行，空间复杂度为 。
详细步骤：
- 时间复杂度 （最好），（最坏）
- 空间复杂度 ：整个过程只使用增量变量等常数个辅助空间。
- 对比参考：直接插入排序平均与最坏时间复杂度均为 ，希尔排序通过分组插入在数据基本有序时避免了大量元素后移，平均性能明显更好。
最终答案：
时间 ~，空间 。