一、希尔排序（Shell Sort）：分组插入，逐步逼近有序

核心思想：

将数组按 步长（gap）分组，对每组执行 插入排序；逐步减小 gap（如 gap = gap // 2），最终 gap=1 时退化为普通插入排序（此时数组已基本有序，插入排序效率高）。

例子：排序数组 [12, 34, 54, 2, 3]

1. 初始数组：[12, 34, 54, 2, 3]（长度 n=5）。

2. 第一步：gap = 5 // 2 = 2（分组，间隔 2 的元素为一组）：

   • 组 1（索引 0, 2, 4）：[12, 54, 3] → 对该组插入排序：
     • 12 是第一个元素，有序；
     • 54 与 12 比较，54>12，不动；
     • 3 与 12 比较（3<12，交换）→ [3, 12, 54]。
   • 组 2（索引 1, 3）：[34, 2] → 插入排序：2<34，交换→ [2, 34]。
   • 数组更新：[3, 2, 12, 34, 54]（组 1 和组 2 的结果拼接）。

3. 第二步：gap = 2 // 2 = 1（退化为插入排序，对整个数组排序）：

   • 从第 2 个元素（2）开始，向前找插入位置：
     • 2 与 3 比较（2<3，交换）→ [2, 3, 12, 34, 54]；
     • 12 与 3 比较（12>3，不动）；
     • 34 与 12 比较（34>12，不动）；
     • 54 与 34 比较（54>34，不动）。
   • 最终数组：[2, 3, 12, 34, 54]（有序）。

希尔排序的特点：

• 时间复杂度：取决于步长序列，平均 O(n¹·³)，最坏 O(n²)（如步长选 n/2 递减）。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：不稳定（分组插入时，相同元素可能因分组被打乱顺序）。

烦人做个题还要说必须开VIP呵呵呵