希尔排序动画演示
按增量分组做插入排序，gap 一轮轮缩小到 1。
键盘：← → 单步 ·空格 播放/暂停 · R 重置 ·Home/End 到两端
希尔排序是插入排序加了「大跨度」的版本。直接插入一次只能挪一格，一个很小的数偏偏排在末尾，就要走完整整 n−1 步。希尔先按增量 gap 把下标相差 gap 的元素算作一组，各组内部做插入排序，一个数一次能跳 gap 格；gap 一轮轮折半，到 1 时序列已经近乎有序，收尾非常快。
这一页按希尔原始序列 n/2、n/4、……、1 走，场景标题上写着当前 gap，同一组的柱子会标出组号、组外的压暗，分组这件事就摆在台面上。它比插入排序快在「先把大逆序对粗粗消掉」，但代价是不稳定，而且复杂度随增量序列变化——原始序列最坏仍是 O(n²)。
希尔排序演示怎么用
- 看 gap：标题里的 gap 就是这一轮的跨度；组内比较永远隔 gap 格，不是隔 1 格。
- 分组切换：每轮从第 0 组做到最后一组，做完一组压暗的那批柱子会换人，跟着高亮看谁跟谁比。
- 读增量：开局那句就把增量序列念出来（例如 16 个数据是 8 → 4 → 2 → 1），中间几轮做完的序列也会整条打印。
- 比一比：同一份倒序数据，先在这一页记下后移次数，再去插入排序页看一次，差距一目了然。
常见问题
增量序列怎么选？n/2 折半是不是更好的？
希尔原始序列写起来最短、也最直观，但最坏情况能退化到 O(n²)。Knuth 的 3h+1、Sedgewick 的序列都有更好的理论上界，代价是不一定整除数组长度。这一页固定用原始序列，就是为了让「gap 一轮轮缩小」这条主线看得清楚。
为什么前几轮做完数组还没排好，但后面就快了？
因为 gap 轮次消除的是距离远的逆序对：一个跨十几格的乱序对，在跨度最大的那轮就被一次跳格的处理掉了。等 gap 到 1 时，剩下的逆序对基本都是相邻的，插入排序消它们几乎不花力气。
希尔排序稳定吗？
不稳定。同一个值可能分在不同轮次的不同组里，被隔着 gap 交换过位置。要稳定就得换归并，或者在关键字之外再带一个原始序号当次级键。