希尔排序是插入排序的改进，按增量分组并逐次缩小至1进行插入排序；Knuth序列（h=3h+1）最常用，初始h通过循环确定，再以h为步长做插入排序。

希尔排序的基本思想与数组实现

希尔排序是插入排序的改进版本，核心在于将原数组按一定间隔（增量）分组，对每组进行插入排序，再逐步缩小增量直到为1。java中用一维数组即可完成，关键在增量序列的选择和分组逻辑。

经典Knuth序列的实现与说明

最常用且稳健的增量序列是Knuth序列：h = 3h + 1，从1开始反向生成不超过数组长度的最大值。例如长度为10的数组，生成过程为 1 → 4 → 13（超限），故取 h = 4，再取 h = 1。

• 先计算初始增量：int h = 1; while (h
• 外层循环控制增量递减：for (; h >= 1; h /= 3)
• 内层按h为步长做插入排序：从索引h开始，逐个将arr[i]插入到其所在h-间隔子序列的正确位置

增量序列对性能的影响

希尔排序的时间复杂度高度依赖增量序列。不同序列带来显著差异：

• 希尔原始序列（N/2, N/4, …）：最坏情况仍为O(N²)，已不推荐
• Knuth序列（1, 4, 13, 40, …）：理论界为O(N^3/2)，实践中稳定高效，适合通用场景
• Sedgewick序列（1, 5, 19, 41, …）：形如4ᵏ + 3×2ᵏ⁻¹ + 1，平均性能更优，但实现稍复杂
• 动态序列（如Hibbard：2ᵏ−1）：保证O(N^3/2)，但常数因子略大

完整可运行示例（Knuth序列）

以下是一个简洁、带注释的Java数组实现：

Java Maven Code Review

审查Java Maven项目（ZIP压缩包或GitLab仓库URL），检查代码规范、命名、模块边界、可维护性问题以及重复代码。

下载

public static void shellSort(int[] arr) {
    if (arr == null || arr.length // 1. 生成最大合法Knuth增量
int h = 1;
while (h = 1; h /= 3) {
    // 对每个h-间隔子序列做插入排序
    for (int i = h; i = h && arr[j - h] > temp) {
            arr[j] = arr[j - h];
            j -= h;
        }
        arr[j] = temp;
    }
}

}

调用 shellSort(new int[]{64, 34, 25, 12, 22, 11, 90}) 即可验证排序效果。

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南