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

第二轮：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（标准插入排序）

最后一步 gap=1，相当于对整个数组进行插入排序，此时数据已经非常接近有序，交换次数极少。

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

四、完整 Java 实现

下面是一个基于 Shell 原始增量序列的 Java 实现。注意代码中处理了空值和边界情况，并使用了通用的包名以便集成。

package com.algorithm.sort;

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 序列在实践中表现良好。希尔排序的实现简单，空间效率高，是值得掌握的经典排序算法之一。