本模块是公共类课程，适合绝大部分计算机岗位。由于 Java 受众最广且易读性强，本模块示例代码使用 Java 编写，其他语言也可参考学习。

希尔排序原理

希尔排序（Shell Sort）是一种基于插入排序的排序算法，通过将数组分成若干子序列分别进行插入排序，从而加快排序速度。希尔排序的核心思想是先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序的时间复杂度在最坏情况下为 O(n^2)，在平均情况下为 O(n log n)，空间复杂度为 O(1)。

希尔排序实现

如，对数组 arr = [5, 3, 8, 6, 4] 进行升序希尔排序。

希尔排序的步骤如下：

1. 选择一个增量序列 gap，通常初始值为数组长度的一半，然后逐步减小 gap 直到为 1。
2. 对每个 gap 进行分组，对每组进行插入排序。

排序过程如下：

1. 初始 gap = 5 >>> 1 | 0 = 2

   得到分组：

   5	3	8	6	4
   组 1	组 2	组 1	组 2	组 3

   对每组进行插入排序：

   • 第一组：[5, 8]
   • 第二组：[3, 6]
   • 第三组：[4]

   排序后：

   5	3	8	6	4

2. gap = 2 >>> 1 | 0 = 1

   当步长为 1 时，排序退化为插入排序。

   流程参考插入排序。

   本轮完成过后，数组排序完成。

希尔排序代码实现

public void shellSort(int[] nums) {
    int n = nums.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = nums[i];
            int j = i;
            while (j >= gap && nums[j - gap] > temp) {
                nums[j] = nums[j - gap];
                j -= gap;
            }
            nums[j] = temp;
        }
    }
}