希尔排序采用“增量分组插入排序”的策略
一、希尔排序
算法逻辑
希尔排序采用“增量分组插入排序”的策略。初始时设定一个增量（通常为数组长度的一半），将相隔该增量的元素组成一个子序列，对每个子序列进行直接插入排序；然后逐步缩小增量（如每次除以2），重复分组和排序过程，直到增量减为1，最后进行一次直接插入排序完成整体有序。
代码实现中，外层循环控制增量变化（从n//2逐渐减至1），内层循环对每个子序列执行插入排序操作。由于前期通过较大增量快速调整元素位置，避免了小元素远距离移动，提高了效率。
defshell_sort(arr):n=len(arr)gap=n//2# 初始增量whilegap>0:foriinrange(gap,n):temp=arr[i]j=i# 对相隔gap的元素进行插入排序whilej>=gapandarr[j-gap]>temp:arr[j]=arr[j-gap]j-=gap arr[j]=temp gap//=2# 缩小增量returnarr算法特性
- 稳定性：不稳定。因为相同元素可能被分在不同子序列中，排序后相对位置可能发生改变。
- 时间复杂度：取决于增量序列的选择，常见情形下约为 $ O(n^{1.3}) $，最坏可达 $ O(n^2) $，但平均性能优于直接插入排序。
- 空间复杂度：$ O(1) $，仅使用常数个辅助变量。
二、快速排序
基本思想
基于分治法：选择一个基准元素（枢轴 pivot），将序列划分为两个子序列——左子序列所有元素 ≤ pivot，右子序列所有元素 ≥ pivot；再递归地对左右两部分进行快排，最终使整个序列有序。
划分过程（Partition）详解
以data[low]作为 pivot，设置两个指针：
i = low（从左向右找大于 pivot 的元素）j = high（从右向左找小于 pivot 的元素）
步骤如下：
- 将 pivot 暂存为
temp = data[low] - 当
i < j时循环：j向前移动，直到找到第一个< temp的元素，将其赋值给data[i]i向后移动，直到找到第一个> temp的元素，将其赋值给data[j]
- 直到
i == j，此时将temp放入data[i]，pivot 归位
defpartition(arr,low,high):pivot=arr[low]i,j=low,highwhilei<j:whilei<jandarr[j]>=pivot:j-=1ifi<j:arr[i]=arr[j]whilei<jandarr[i]<=pivot:i+=1ifi<j:arr[j]=arr[i]arr[i]=pivotreturnidefquick_sort(arr,low,high):iflow<high:pi=partition(arr,low,high)quick_sort(arr,low,pi-1)quick_sort(arr,pi+1,high)算法特性
- 稳定性：不稳定（交换过程中相同元素顺序可能被打乱）
- 时间复杂度：平均 $ O(n \log n) $，最坏 $ O(n^2) $（已有序时退化）
- 空间复杂度：$ O(\log n) $（递归调用栈深度）
- 希尔排序的性能在很大程度上依赖于所采用的增量序列（gap sequence）。不同的增量序列会显著影响排序的比较和移动次数，从而改变其实际运行效率。
一、常见的增量序列
Shell 原始序列（最原始）
- 增量公式：$ d_k = \left\lfloor \frac{n}{2^k} \right\rfloor $，每次除以 2
- 示例（n=8）：8 → 4 → 2 → 1
- 特点：简单直观，但性能一般，最坏时间复杂度为 $ O(n^2) $
Knuth 序列
- 增量公式：$ d_k = \frac{3^k - 1}{2} $，从大到小取不超过 n 的值
- 示例：1, 4, 13, 40, 121, …
- 实际使用时逆序应用：如对长度为100的数组，用 40 → 13 → 4 → 1
- 时间复杂度约为 $ O(n^{1.5}) $
- 是较优的选择之一，被广泛推荐
Hibbard 序列
- 增量公式：$ 2^k - 1 $，即 1, 3, 7, 15, 31, …
- 可证明最坏情况时间复杂度为 $ O(n^{3/2}) $
- 对某些数据分布表现良好
Sedgewick 序列
- 定义复杂，形式为：1, 5, 9, 17, 29, 77, … （有多种构造方式）
- 例如：$ { \max(2^i \cdot 3^j) < n } $ 或特定公式生成
- 经实验验证具有非常好的平均性能，时间复杂度接近 $ O(n^{4/3}) $
- 被认为是实践中最优的增量序列之一
Ciura 序列（经验序列）
- 预定义的经验值：1, 4, 10, 23, 57, 132, 301, 701, …
- 不基于数学公式，而是通过大量实验优化得出
- 在实际应用中表现极佳，常用于现代实现中
二、不同增量序列对性能的影响
| 增量序列 | 最坏时间复杂度 | 平均性能 | 说明 |
|---|---|---|---|
| Shell 原始（÷2） | $ O(n^2) $ | 较差 | 当相邻元素分布在不同组时效率低，易退化 |
| Knuth | $ O(n^{1.5}) $ | 中等偏上 | 结构合理，适合教学与一般用途 |
| Hibbard | $ O(n^{3/2}) $ | 较好 | 理论保障较好，避免部分退化情况 |
| Sedgewick | $ O(n^{4/3}) $ | 很好 | 实验性能优秀，适合高性能需求场景 |
| Ciura（经验） | 未知（但非常快） | 极佳 | 当前公认最快的实用序列 |
⚠️ 注意：所有增量序列都必须保证最后一个增量为 1，以确保最终进行一次完整的插入排序，使数组完全有序。
三、代码示例（使用 Knuth 序列）
defshell_sort_knuth(arr):n=len(arr)# 生成 Knuth 增量序列：(3^k - 1)/2 < ngap=1while(3*gap+1)<n:gap=3*gap+1# 得到最大的小于 n 的 Knuth 数whilegap>=1:foriinrange(gap,n):temp=arr[i]j=iwhilej>=gapandarr[j-gap]>temp:arr[j]=arr[j-gap]j-=gap arr[j]=temp gap//=3# 回退到前一个 Knuth 数returnarr总结
- 增量序列决定了希尔排序的分组策略；
- 更科学的序列（如 Ciura、Sedgewick）能大幅提高效率；
- 教学中常用 Shell 原始序列或 Knuth 序列；
- 实际工程中建议使用 Ciura 等经验序列以获得最佳性能。