-希尔排序
并非希儿排序（）
其实是分组的插入排序，通过分组让元素实现跳跃式移动，减少逆序对数量。
一、算法步骤
1.确定增量序列（Gap Sequence）
选择递减的增量序列：gap₁ > gap₂ > ... > gapₖ = 1
常用增量序列：
Shell原始序列：gap = n/2, n/4, ..., 1
Hibbard序列：2ᵏ - 1（1, 3, 7, 15, ...）
Knuth序列：3k + 1（1, 4, 13, 40, ...）
Sedgewick序列：更复杂的优化序列
2.分组插入排序
对于每个增量gap：
将数组分为gap个子序列
每个子序列由相隔gap的元素组成
对每个子序列进行插入排序
3.逐步缩小增量
每次减少gap，重复分组排序
直到gap = 1，执行最后一次标准的插入排序
代码：
class Solution { public: vector<int> sortArray(vector<int>& nums) { int n = nums.size(); for(int gap = n >> 1; gap; gap >>= 1){ for(int i = gap;i < n; i++){ int j = i - gap; int x = nums[i]; while(j >= 0 && x < nums[j]){ nums[j + gap] = nums[j]; j -= gap; } nums[j + gap] = x; } } return nums; } };二、所用到的思想
希尔排序虽然不是典型的分治算法（如归并、快排），但它巧妙地运用了分治的核心思想：
1.分解（Divide）
for(int gap = n >> 1; gap; gap >>= 1)分解方式：按照
gap值将原数组分解成多个子序列分解粒度：从
n/2开始，每次减半，直到1子序列特点：
当
gap=4时：分解为4个子序列子序列1：nums[0], nums[4], nums[8], ...
子序列2：nums[1], nums[5], nums[9], ...
子序列3：nums[2], nums[6], nums[10], ...
子序列4：nums[3], nums[7], nums[11], ...
每个子序列元素间隔为
gap
2.解决（Conquer）
for(int i = gap; i < n; i++) { int j = i - gap; int x = nums[i]; while(j >= 0 && x < nums[j]) { nums[j + gap] = nums[j]; j -= gap; } nums[j + gap] = x; }独立解决：对每个子序列独立进行插入排序
局部有序：每个子序列内部变得有序
关键特性：子序列之间不互相干扰
当处理nums[i]时，只与同子序列的前一个元素nums[i-gap]比较
子序列之间的元素不直接比较
3.合并（Combine）
希尔排序的"合并"是隐式的：
无需显式合并：因为排序是原地进行的
渐进合并：随着
gap减小，子序列逐渐融合最终合并：当
gap=1时，所有元素在同一个子序列中，完成最终排序。
三、希尔排序分治思想的优势
1.空间效率
原地排序，不需要归并排序的额外数组
空间复杂度O(1)
2.时间效率
早期的大gap快速消除远处逆序对
后期的小gap精细调整局部顺序
比直接对整个数组做插入排序高效得多