希尔排序采用“增量分组插入排序”的策略

一、希尔排序
算法逻辑
希尔排序采用“增量分组插入排序”的策略。初始时设定一个增量（通常为数组长度的一半），将相隔该增量的元素组成一个子序列，对每个子序列进行直接插入排序；然后逐步缩小增量（如每次除以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 的元素）

步骤如下：

1. 将 pivot 暂存为temp = data[low]
2. 当i < j时循环：
   • j向前移动，直到找到第一个< temp的元素，将其赋值给data[i]
   • i向后移动，直到找到第一个> temp的元素，将其赋值给data[j]
3. 直到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）。不同的增量序列会显著影响排序的比较和移动次数，从而改变其实际运行效率。

一、常见的增量序列

1. Shell 原始序列（最原始）

   • 增量公式：$ d_k = \left\lfloor \frac{n}{2^k} \right\rfloor $，每次除以 2
   • 示例（n=8）：8 → 4 → 2 → 1
   • 特点：简单直观，但性能一般，最坏时间复杂度为 $ O(n^2) $

2. Knuth 序列

   • 增量公式：$ d_k = \frac{3^k - 1}{2} $，从大到小取不超过 n 的值
   • 示例：1, 4, 13, 40, 121, …
   • 实际使用时逆序应用：如对长度为100的数组，用 40 → 13 → 4 → 1
   • 时间复杂度约为 $ O(n^{1.5}) $
   • 是较优的选择之一，被广泛推荐

3. Hibbard 序列

   • 增量公式：$ 2^k - 1 $，即 1, 3, 7, 15, 31, …
   • 可证明最坏情况时间复杂度为 $ O(n^{3/2}) $
   • 对某些数据分布表现良好

4. Sedgewick 序列

   • 定义复杂，形式为：1, 5, 9, 17, 29, 77, … （有多种构造方式）
   • 例如：$ { \max(2^i \cdot 3^j) < n } $ 或特定公式生成
   • 经实验验证具有非常好的平均性能，时间复杂度接近 $ O(n^{4/3}) $
   • 被认为是实践中最优的增量序列之一

5. Ciura 序列（经验序列）

   • 预定义的经验值：1, 4, 10, 23, 57, 132, 301, 701, …
   • 不基于数学公式，而是通过大量实验优化得出
   • 在实际应用中表现极佳，常用于现代实现中

二、不同增量序列对性能的影响

⚠️ 注意：所有增量序列都必须保证最后一个增量为 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 等经验序列以获得最佳性能。