介绍
希尔（Shell）排序，是 插入排序 的 高效 改进版。过 分组 预排序 让数组整体接近有序，最后用普通 插入排序 完成最终排序，大幅降低插入排序的移动次数，时间效率远高于基础插入排序。
普通插入排序的缺点是
数组 无序程度越高、元素个数越多，元素需要 移动的次数就越多（比如一个很小的数在数组末尾，需要一步步移到开头）。
希尔排序算法
希尔排序针对这个问题做了优化，核心是 步长（gap）分组：
- 选择一个步长序列（比如n/2、n/4、n/8…1，n 是数组长度），按步长将数组分成多个子组；
- 对每个子组分别做插入排序（分组预排序），让数组整体逐渐接近有序；
- 逐步缩小步长，重复 “分组 + 插入排序”，直到步长为1；
- 步长为1时，整个数组就是一个子组，此时做一次普通插入排序（数组已接近有序，这次排序几乎无额外移动）。
提示： 一般取 n/2，如果结果为偶数，则加 1
例子
已序列 [49,38,65,97,76,13,27,48,55,4] 为例（长度为 10），进行排序演示
第1阶段
分组
步长 gap = 10(第一次根据元素数量)//2 = 5，索引差为 5 的元素分为一组，共分成 5 组（每组 2 个元素），分组结果如下：
分组情况 :
- 组 1：索引
0与索引5组成一组，即：[49,13] - 组 2：索引
1与索引6组成一组，即：[38,27] - 组 3：索引
2与索引7组成一组，即：[65,48] - 组 4：索引
3与索引8组成一组，即：[97,55] - 组 5：索引
4与索引9组成一组，即：[76,4]
排序
执行循环，对每个 子组 执行 插入排序
- 对 组1
[49,13]执行插入排序，由于49>13，将这两个元素 互换位置，执行后数组：[13,38,65,97,76,49,27,48,55,4] - 对 组2
[38,27]执行插入排序，由于38>27，将这两个元素 互换位置，执行后数组：[13,27,65,97,76,49,38,48,55,4] - 对 组3
[65,48]执行插入排序，由于65>48，将这两个元素 互换位置，执行后数组：[13,27,48,97,76,49,38,65,55,4] - 对 组4
[97,55]执行插入排序，由于97>55，将这两个元素 互换位置，执行后数组：[13,27,48,55,76,49,38,65,97,4] - 对 组5
[76,4]执行插入排序，由于76>4，将这两个元素 互换位置，执行后数组：[13,27,48,55,4,49,38,65,97,76]
本次结果：
[13,27,48,55,4,49,38,65,97,76]
第2阶段
分组
步长 gap = 5(上一次的步长)//2 = 2，索引差为 5 的元素分为一组，共分成 2 组（每组 5 个元素），分组结果如下：
分组情况 :
- 组 1（偶数索引：0、2、4、6、8）→ [13,48,4,38,97]
- 组 2（奇数索引：1、3、5、7、9）→ [27,55,49,65,76]
对 组1 排序
对 组1 [13,48,4,38,97] 执行 插入排序，初始时：
- 已排序序列：
13 - 未排序序列：
48,4,38,97
1.执行内层循环，比较 未排序的首元素 48，与 已排序序 的 元素逐一比较
- 与 已排序序列最后一个元素：
13比较，因为48>13，所以应该将48插入到13的后面，由于原本顺序就是这样，所以不动。
本轮结果：：[13,48,4,38,97]
已排序序列：
13,48未排序序列：
4,38,97
2.执行内层循环，比较 未排序的首元素 4，与 已排序序 的 元素逐一比较
与 已排序序列最后1个元素：
48比较，因为48>4，所以应该将48后移到4的位置，数组变为：[13,27,48,55,48,49,38,65,97,76]与 已排序序列第1个元素：
13比较，因为13>4，所以应该将13后移到48的 原位置，数组变为：[13,27,13,55,48,49,38,65,97,76]已遍历完 已排序序列，将
4插入到13的位置，数组变为：[4,27,13,55,48,49,38,65,97,76]
本轮结果：：[4,13,48,4,38,97]
- 已排序序列：
4,13,48
- 未排序序列：
38,97
后面执行过程略
对 组2 排序
执行过程同 组1
此时结果：[4, 27, 13, 49, 38, 55, 48, 65, 97, 76]
第三阶段
分组
步长 gap = 2(上一次的步长)//2 = 1，索引差为 1 的元素分为一组，此时执行的就是 普通插入排序，但因为数组已 基本有序，几乎没有大量元素移动，这也是希尔排序高效的关键。
执行过程，同插入排序，略
最终结果：[4, 13, 27, 38, 48, 49, 55, 65, 76, 97]
时间复杂度
O(n^2)
最好
O(n^{1.25})
最坏
O(n^2)（但实际工程中几乎不会出现）
平均
O(n^{1.3})
空间复杂度
O(1)
是否稳定
不稳定，因为跨 n 个元素取值