希尔排序算法详解：原理、实现与优化

第二轮：gap=2

将数组分为 2 组：(3,1,0,9,7), (5,6,8,4,2)

分组示意图：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 3 │   │ 1 │   │ 0 │   │ 9 │   │ 7 │   │ → (3,1,0,9,7)
│   │ 5 │   │ 6 │   │ 8 │   │ 4 │   │ 2 │ → (5,6,8,4,2)
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

排序后结果：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 2 │ 1 │ 4 │ 3 │ 5 │ 7 │ 6 │ 9 │ 8 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

第三轮：gap=1（标准插入排序）

最终排序结果：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

四、完整 Java 实现

package com.kwan.springbootkwan.controller;

public class ShellSort {
    /**
     * 基础希尔排序（使用 Shell 原始增量序列）
     * @param arr 待排序数组
     */
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        // 初始 gap 为数组长度的一半，逐步缩小 gap 直到 1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 从第 gap 个元素开始，对各个子序列进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                // 对子序列进行插入排序
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }

    // 测试代码
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("原始数组:");
        printArray(arr);
        System.out.println("\n希尔排序后:");
        shellSort(arr);
        printArray(arr);
    }

    // 打印数组
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

五、算法分析

时间复杂度分析

希尔排序的时间复杂度取决于增量序列的选择：

空间复杂度

• 只需要常数级别的额外空间
• 空间复杂度：O(1)

稳定性

希尔排序是不稳定的排序算法，因为相同的元素可能会被分到不同的子序列中，导致相对顺序改变。

六、实际应用场景

1. 中等规模数据排序：当数据量在几千到几万时，希尔排序表现良好
2. 嵌入式系统：由于空间复杂度低，适合资源受限的环境
3. 作为更复杂算法的预处理步骤：可以先使用希尔排序进行部分排序

七、与其他排序算法的对比

八、总结

希尔排序通过分组插入排序的思想，有效减少了数据移动的次数，是对简单插入排序的重要改进。虽然其时间复杂度理论分析较为复杂，但在实际应用中，特别是中等规模数据的排序场景下，希尔排序往往能提供不错的性能表现。

选择合适的增量序列对希尔排序的性能至关重要，Hibbard 序列和 Sedgewick 序列在实践中表现良好。希尔排序的实现简单，空间效率高，是值得掌握的经典排序算法之一。