在排序算法这个“老赛道”里快排、归并、堆排序几乎霸占了所有流量。希尔排序属于那种原理不难、实战效果却不差的选手可惜很多人只在教材目录里见过它。第一次自己实现它时的感受就是代码短得不像一个性能优化型算法但跑起来的数据却让人意外。希尔排序不是解决“最坏情况”的王者也不是分布式场景里的常客它是单机小内存场景下凭借极简单的代码量换取排序效率的一个非常好用的选择。这篇文章不聊面试八股只记录我实际实现、测速、踩坑过程中的观察适合那些想把排序原理弄扎实或者想在嵌入式、脚本环境里快速拿到一份体面排序代码的读者。1. 希尔排序到底在解决什么问题1.1 插入排序的“短板”在哪插入排序的逻辑再简单不过从左到右扫描把每个元素往已经排好序的左侧插进去。这个算法在“基本有序”的小数组上快得惊人但它有个致命问题——元素每次只能往后挪一位。我给你一个反例数组[5, 4, 3, 2, 1, 0]你要把 0 拿到最前面它得一路跟前面五个元素逐一比较每个元素都得它挪一个位置总共产生 15 次移动才能排完。这还只是 6 个元素当数据量到一万、十万的时候这种“一步一挪”的方式会直接把程序拖垮。学算法的人喜欢用一个概念衡量这种低效逆序对。只要前面存在一个比后面大的元素就算一对逆序。插入排序的一次移动本质上是消除一个逆序对。想一想如果每次移动只能消除一对逆序那总移动次数就跟逆序对数量直接挂钩而随机数组的逆序对数量基本是 O(n²) 级别的。所以插入排序在随机数据上跑起来就特别吃亏。但这里有个观察很有价值如果数组已经“大体有序”逆序对数量很少插入排序几乎是线性的。这就好比黑板上的乱涂乱画如果只是个别线条位置不对拿橡皮局部修一下就好如果整张纸都是乱线条你需要的不是橡皮而是一把大刀。1.2 跳跃式插入的核心思想希尔排序的核心思路就是先把数组按一个固定间隔 gap 分成若干“小组”每个小组内部做插入排序。比如数组长度是 9先取 gap4那么位置 0、4、8 是一组位置 1、5 是一组位置 2、6 是另一组位置 3、7 是最后一组。先让每组内部有序然后缩小 gap比如变成 2继续对位置 0、2、4、6、8 和位置 1、3、5、7 分别排序。最后 gap1做一次普通插入排序收尾。你可能会问前面那些分组排序不是白折腾吗不是的。想象一个降序数组[9,8,7,6,5,4,3,2,1]如果直接插排最小的 1 要一路从末尾挪到开头长途迁徙。但希尔排序在 gap4 那一步就已经让 9、5、1 这一组变成 1、5、9也就是说 1 一下子跨越了 4 个位置。虽然还没到最终位置但已经走了很大一段路。随着 gap 逐步缩小元素每次移动的幅度也在缩减最后 gap1 时数组已经接近有序只需要少量比较和移动就能完工。这个思想可以类比相机的变焦镜头先用大倍率粗扫快速锁定大致范围再慢慢调小倍率精修。希尔排序就是“大步粗调 小步精修”的组合策略通过多轮不同颗粒度的排序把插入排序的短板一次性补上。1.3 希尔排序能做什么、适合谁希尔排序特别适合那些“想用最小代码量换来整体性能提升”的场景。它不需要额外开辟大块内存原地排序辅助空间是 O(1)代码实现起来也就十几行对于中小规模数据比如几千到几十万条记录它的表现往往比纯插入排序快一个到两个数量级。很多嵌入式场景里不方便引入库函数或者运行时环境对递归栈深度有限制这个时候快排和归并未必是最好的选择希尔排序反而是最顺手的一个。它的稳定性要求不算高内存也吃紧这时候你会感谢希尔排序的轻量。如果你是在普通 PC 上处理上百万数据还是老老实实用工程化的内建排序但如果你想彻底理解排序算法怎么从“笨重”走向“实用”希尔排序是绕不开的一块基石。2. 增量序列的选择是一场取舍2.1 为什么步长不能随便定希尔排序的代码结构看起来很固定真正的学问全在增量序列上。增量序列就是排序过程中一步步缩小的 gap 值序列。最简单的写法是n/2, n/4, n/8, ..., 1也就是每轮把 gap 减半。这种写法最容易记也最容易写错因为它可能让算法退回到 O(n²) 的复杂度。问题出在哪儿如果 gap 序列设计得不好有些元素在整个排序过程中始终没机会发生足够远的交叉移动导致前几轮分组排序对整体逆序数的削减非常有限最后 gap1 时还是要靠普通插入排序“硬扛”那就前功尽弃了。举个例子gap 序列如果一直保持偶数间隔奇数位置和偶数位置在很长一段时间内互不往来就会出现一种“局部各自有序、全局还很乱”的尴尬局面。所以增量序列的好坏直接决定希尔排序是“超值”还是“白忙活”。这也是为什么算法教材里对增量序列讨论得特别仔细因为它的复杂度上限取决于增量之间的比例关系而不是单纯的代码循环。2.2 几种常见增量序列的横向对比我整理了一下实际碰到的几类增量序列它们各有各的脾气。序列名称生成方式常见复杂度参考实际印象经典减半序列gap n/2每轮gap / 2最坏可退化到 O(n²)代码最简单教学演示合适但性能上限一般Knuth 序列h1; while hn/3: h3*h1常被视为约 O(n^(3/2))实现也不难工程上很常用稳定性比减半好Hibbard 序列2^k - 1即 1、3、7、15...约 O(n^(3/2))理论性质清晰跑出来的效果和 Knuth 接近Sedgewick 序列常见一组1、8、23、77、281...文献中更优的上界约 O(n^(4/3))实测通常更好但推出规则稍复杂Ciura 序列1、4、10、23、57、132、301...没有严格证明的最坏上界实测性能好很多竞赛选手爱用这里面有个很容易被误解的点表格里的复杂度只是“常见记载”或“经验参考”不是所有教材都给出完全一致的结论。因为希尔排序的复杂度分析极度依赖增量序列的数学性质直到今天仍然缺少一个统一的“最优增量公式”。这不影响我们使用但提醒你不要轻信网上一句“希尔排序是 O(n log n)”之类的话它通常是“某个特定增量序列下的平均表现”不是普遍结论。2.3 工程选型建议如果你只是教学演示或者临时写个排序工具直接用减半序列最省心。代码短逻辑透明别人一看就懂。但如果你想在实际项目里用希尔排序我建议至少换成 Knuth 序列因为它可以用三行代码生成性能又有肉眼可见的提升。一个很实用的习惯是把增量序列预生成到一个数组里排序时倒序遍历。这样即使增量公式调整也只是改一个生成函数不用动主逻辑。我在生产环境里写希尔排序时基本都采用“预生成增量数组”的方式可控性比边排序边算 gap 高很多。后面我会在代码里演示这个写法。3. 三种场景的简单实现与手算拆解3.1 Python 版本逻辑最直白的一段代码先上一个最简单、最经典的 Python 实现增量序列就用n//2减半到 1便于理解整个流程。def shell_sort(arr): n len(arr) gap n // 2 while gap 1: for i in range(gap, n): temp arr[i] j i while j - gap 0 and arr[j - gap] temp: arr[j] arr[j - gap] j - gap arr[j] temp gap // 2 return arr这段代码的骨架就是“一个外层的 gap 循环 一个带 gap 间隔的插入排序”。内部这段和普通插入排序的区别只在于普通插入排序每次和左边的相邻元素比较这里和左边隔了 gap 个位置的元素比较。temp先保存当前值避免被前面的元素覆盖arr[j] arr[j - gap]是往后平移不是交换这样能省掉很多临时变量操作。我用一个随机数组跑了一下输入[64, 34, 25, 12, 22, 11, 90] 输出[11, 12, 22, 25, 34, 64, 90]减半序列对中小数组的排序效果已经够用。如果你想替换成 Knuth 增量只需要把 gap 的生成改成def shell_sort_knuth(arr): n len(arr) h 1 while h n // 3: h 3 * h 1 while h 1: for i in range(h, n): temp arr[i] j i while j - h 0 and arr[j - h] temp: arr[j] arr[j - h] j - h arr[j] temp h // 3 return arrKnuth 序列的生成逻辑很友好先从 1 开始不断乘以 3 再加 1直到接近n/3排序时再一路整除 3 退回去。这样初始间隔不会超过数组长度的三分之一扫描次数更合理。3.2 Java 版本与边界讨论Java 版本和 Python 逻辑完全一致但边界条件必须更小心。我贴一个常用实现public static void shellSort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int temp arr[i]; int j i; while (j gap arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } } }这里有几个边界点新手特别容易踩外层for的结束条件是gap 0不是gap 1。因为 gap 是 int最后一次gap / 2后可能直接变成 0用gap 0最安全。内层 while 必须把j gap写在arr[j - gap] temp之前因为 Java 会先判断左边的表达式如果 j 已经小于 gap再访问j - gap就会数组越界。顺序反了直接崩。temp一定要在进入内层循环前保存好因为arr[i]的位置随时可能被覆盖。保存晚了会把原始值丢掉。我还喜欢在这类代码里额外加一个“空数组和单元素数组”的判断很多库函数不会主动处理这种情况但自己写排序时最好养成防御习惯。3.3 手算演示从逆序数组看分组排序文字讲再多不如看一个完整例子。我拿最极端的降序数组[9, 8, 7, 6, 5, 4, 3, 2, 1]数组长度 9用减半序列 gap4、2、1 过一遍。gap4分成四组位置 0、4、8数字 9、5、1排序后变为 1、5、9位置 1、5数字 8、4排序后变为 4、8位置 2、6数字 7、3排序后变为 3、7位置 3、7数字 6、2排序后变为 2、6一轮之后数组变成[1, 4, 3, 2, 5, 8, 7, 6, 9]。注意最右边的 1 直接飞到最左边这一下就消掉了至少 8 个逆序对。gap2分成两组位置 0、2、4、6、8数字 1、3、5、7、9已经有序不用动位置 1、3、5、7数字 4、2、8、6插入排序之后变成 2、4、6、8数组整体变成[1, 2, 3, 4, 5, 6, 7, 8, 9]。gap1做标准插入排序。此时数组已经天然有序每个元素只需要和左边一个元素比较一次移动次数几乎为零。整个过程中 1 的迁移路径是“先跳 4 格再跳 1 格”加起来不到 5 次而普通插入排序里它需要一路挪 8 次。这就是希尔排序用“跳着排”换取全局有序的道理。4. 性能实测、稳定性与适用边界4.1 实测观察数据量和增量带来的变化我习惯用 Python 的timeit模块做简单对比把同一个随机数组复制成两份分别跑插入排序和希尔排序。网上很多计时结果差异巨大其实跟机器、解释器版本、数组生成方式都有关系所以我更看重相对差距而不是某个绝对毫秒数。在我常用的笔记本上1 万个随机整数简单插入排序大约要几百毫秒经典的减半希尔排序只需要十几毫秒差距在十倍以上。把数据量提到 10 万插入排序直接涨到十几秒而希尔排序通常在几百毫秒这个量级。你可以把这个趋势记在心里数据越大希尔排序的领先幅度越明显但它不会像快排那样飞得更高只是“稳”。如果想自己复现注意一个细节timeit里每次排序前都得复制数组因为排序是原地操作跑完一次后数组已经有序再测第二次就会出现“对有序数组排序”的假象时间会变得特别好看但那不是真实性能。import timeit import random raw [random.randint(0, 100000) for _ in range(10000)] t1 timeit.timeit(lambda: sorted(raw[:]), number10) t2 timeit.timeit(lambda: shell_sort(raw[:]), number10)把number设成多次取平均结果比对才有参考性。4.2 稳定性、内存与并行化限制希尔排序有一个经常被忽略的弱点它不稳定。这一点在业务排序里可能很要命。什么叫不稳定就是两个相等元素的相对顺序可能被改变。普通插入排序遇到相等元素时不交换所以稳定但希尔排序在分组排序时相等的元素可能落在不同分组里或者同一分组内因为跳跃移动而改变先后关系。我举个例子数组[5a, 8, 5b, 2]假设 5a 和 5b 相同但用a、b标记原始顺序。gap2 时位置 0 和 2 的元素5a、5b会进行比较和排序最终可能变成5b在前5a在后相等元素的先后顺序被打乱。如果你的业务数据里有“按时间排序后再按类型排序”的需求这种不稳定性会直接影响结果。另外希尔排序是原地算法额外内存几乎不计这点比归并强太多。但它对缓存并不友好因为访问元素时跨度很大动不动就跳几百个下标。数据量特别大的时候缓存命中率下降反而会被快排这类“局部性更好”的算法超越。并行化就更不用想了每个分组内部虽然有独立性但分组数量随着 gap 缩小而变化不好拆分线程。4.3 和插入排序、快速排序的比较把希尔排序和插入排序摆在一起看关系一目了然希尔就是“多轮插入排序”。插入排序的优点是稳定、简单、局部有序时效率高缺点是全局乱序时复杂度高。希尔排序保留了“简单”的优点牺牲了稳定性换来了全局性能的大幅提升。和快速排序比通常快排在大数组上更猛因为平均复杂度更优而且经过优化的 introsort 版本几乎无死角。但快排有最坏情况 O(n²)也就是对某些特定排列会退化标准库里的实现会通过三数取中、切换到插排等方式规避那段代码非常复杂。希尔排序没有递归调用没有栈空间风险在最坏情况下也只是回归到 O(n²)不会爆栈不会系统崩溃。在一些“不知道数据长什么样”的偏门环境里这种“坏也坏不到哪里去”的性格反而是个优点。5. 踩坑记录与真正能帮你优化的细节5.1 容易忽略的三个坑第一个坑gap 最后没能减到 1。有人把外层循环写成while gap 1然后 gap 每次减半当 gap 从 2 变到 1 时外层直接退出导致数组永远缺一次完整插入排序。少跑一轮的结果是“看起来排得挺整齐但肯定没排完”而且这种 bug 在小数组上往往不容易被发现因为局部有序掩盖了问题。第二个坑用交换代替平移。很多初学者写的插入排序喜欢用swap元素而不是后移整体这在普通插入排序里还能忍在希尔排序里会显著拖慢速度。每次交换要三次赋值而平移只需要一次读写。数据量大时这个差距会变得更明显。第三个坑增量序列的“最优迷信”。看到网上有人说用了某个序列就变成 O(n log n)于是照搬结果发现某些数据上表现很差。这是因为复杂度结论有前提条件不一定适用于你的数据分布。正确做法是固定数据集上做 A/B 测试用timeit对比几个序列别再被公式牵着走。5.2 工程上的折中什么时候该用它很多人纠结希尔排序和标准库排序到底选谁。我的经验是如果项目环境允许直接使用成熟的排序库比如 Python 的sorted、Java 的Arrays.sort那别折腾直接用。因为这类库是无数人测试、优化过的稳如老狗。但如果你碰上以下情况希尔排序的优势就出来了嵌入式环境内存极有限不能开额外数组又不能依赖系统库数据量在几十万以内不想为了排序引入复杂的递归逻辑除了排序还要做很多其他逻辑想用几行代码搞定不引入额外依赖对稳定性没有硬性要求纯按数值或者简单 key 排序我记忆中最好用的一次是在一个资源受限的小设备上没有现成的排序函数快排递归栈又有风险最后用希尔排序二十行内解决跑得很顺畅。类似的场景里它就像一把可以随身带的瑞士军刀不花哨但关键时刻真能用上。5.3 几个值得继续深挖的方向希尔排序看着简单但继续深挖的空间很大。增量序列的数学性质是其一这个方向会引出一堆组合数学和数论问题适合琢磨算法本质的人去研究。梳排序是另一个值得对比的算法它和希尔排序思想类似把“逐步缩小间隔”应用到冒泡排序上实现思路很有意思。另外希尔排序的代码变形非常多有的会预先算好增量数组有的会从固定序列里倒着选有的会加入哨兵值避免边界判断。你完全可以根据自己的数据特征调整出一个版本。我的建议是先把减半序列写熟再换 Knuth 序列最后试着实现 Sedgewick 序列每换一次都会对排序底层多一分理解。最后说点个人偏好当我在一个不太依赖标准库的嵌入式环境里需要手写排序我直接选 Knuth 增量加希尔排序当需求很紧只是要一个可用的快速代码就回到gap n/2。希尔排序不会让你在每一轮 benchmark 里全胜但它在可维护性、空间开销和代码稳定性上足够让人安心。希望这篇记录对你的实现有帮助如果你也试过其他增量序列跑完数据后来聊聊实际感受。