排序算法 SHELL SORT
希尔排序.
按递减间隔分组插入，最后以间隔 1 完成排序。
时间最坏 O(n²)（折半间隔）额外空间O(1)稳定性不稳定
原理与执行逻辑
按照 gap 将下标分组，对每组执行插入排序，再逐步缩小 gap。较大的间隔先移动远距离逆序元素，最后用 gap = 1 完成排序。
执行步骤
- 以数组长度的一半作为初始间隔。
- 从下标 gap 开始，将元素与前方相隔 gap 的元素比较并交换。
- 完成当前间隔的所有分组后，将 gap 折半。
- 完成间隔 1 的插入排序后结束。
关键理解
每轮结束后，各个相隔 gap 的子序列都有序，整个数组可能仍无序。时间复杂度取决于间隔序列，跨组移动也可能影响稳定性。
简短示例
[8, 3, 6, 1] 在 gap = 2 时处理下标组 [0, 2] 与 [1, 3]，得到 [6, 1, 8, 3]；gap = 1 时再排成升序。
代码与执行动画
STEP 0 / 63function shellSort(arr) { for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) { for (let i = gap; i < arr.length; i++) { let j = i; while (j >= gap && arr[j - gap] > arr[j]) { [arr[j - gap], arr[j]] = [arr[j], arr[j - gap]]; j -= gap; } } } return arr;}高亮对应当前步骤；源码对传入数组进行原地排序。
数组状态
升序 · 8 个元素比较 0实际交换 0数组写入 0当前区间 —
待排序当前操作已就位
下标显示在底部；柱体随元素移动，等值元素也保留独立身份。
0
准备排序
点击下一步或自动播放，观察数组从左到右升序排列的过程。
调整待排序数组
使用相同数据切换算法，观察比较与交换过程。
希尔排序的执行规则
本实现使用 n/2、n/4、…、1 的折半间隔，不同间隔序列的复杂度不同。
交换次数仅统计两个不同位置的交换；可输入重复值。对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目75. 颜色分类打开题目
通用排序应用，可用希尔排序实现；题目不专门考查步长序列，进阶的一趟扫描要求需另写算法。