1. 排序问题与算法选型思路排序大概是每个程序员最早接触、也最绕不开的基础问题。数据库里要排序搜索引擎要排序前端渲染列表要排序甚至你用手机通讯录按拼音找人背后也是排序。而在经典的数据结构课程里直接插入排序和希尔排序总是被放在一起讲我当年学的时候其实不太理解为什么后来带了不少新人、自己也重新啃了几轮算法才真正看懂这两兄弟的价值。先亮个观点直接插入排序是理论最优的小规模排序方案而希尔排序则是插入思想从逐个挪动升级成跳跃式插入的一次漂亮进化。很多人觉得这两个算法简单笔试面试也考得不算多所以不怎么上心。但恰恰是这种看起来简单的算法最考验基本功。我自己面试别人的时候经常让候选人手写插入排序然后追问一句希尔排序的增量序列为什么这样取能答清楚的人真的不多。这篇东西适合谁看呢第一类是正在学数据结构、准备考研或刷题的学生你需要的是把原理吃透、把代码写稳第二类是工作了一两年、写业务写得多但基础有点生疏的开发建议把这两个排序重新捡起来对你理解分治、理解复杂度、理解稳定性这个概念都有帮助第三类是准备面试的人插入排序和希尔排序在面试里出现频率并不低尤其是希尔排序不同增量序列的性能差异经常被拿来考察你到底是背答案还是真懂。在正式拆之前我想先给你吃颗定心丸这两个算法都不难但很容易写错。我见过太多人在插入排序的while循环里把边界写崩、在希尔排序的gap递增/递减方向搞反代码跑出来结果错得一塌糊涂。所以这篇文章我会按思路 - 过程推演 - 完整代码 - 坑点的顺序来讲争取让你看完就能自己写对。先说一下整体选型逻辑。很多人问既然以后有大把的排序函数可以直接调用比如Java里的Arrays.sort()、Python里的sorted()、数据库里的ORDER BY为什么还要学这些土办法原因有三个第一排序函数内部用的是TimSort或Dual-Pivot QuickSort这类复杂算法但它们在小规模数据或近乎有序的数据上底层依然会退回到插入排序逻辑第二理解基础排序能帮你看懂复杂排序的优化动机比如归并排序为什么稳定、快排为什么不稳定这些特征追根溯源都跟最朴素的比较/交换方式有关第三有些场景确实需要你手写排序比如嵌入式环境、不允许用库函数的笔试、需要自定义排序逻辑的框架内部。那具体到插入排序和希尔排序它们在真实项目里的分工是这样数据量很小几十个以内时插入排序的常数极低甚至比快排还快数据量稍大但近乎有序时插入排序依然很强势。希尔排序则更适合中等规模、有一定乱序程度但没到完全随机洗牌的数据它可以在不引入额外内存的前提下把排序速度提升到一个令人满意的水平。这两个算法都不需要额外数组属于原地排序这在内存受限的环境里是加分项。接下来我先把直接插入排序完整地过一遍然后再引出希尔排序因为希尔排序的思想完全建立在直接插入排序之上你前面没吃透后面就跟不上。2. 直接插入排序原理、推演与实现细节2.1 核心思想像摸扑克牌一样整理手牌你玩过斗地主或者德州扑克吗起牌的时候大多数人会一张一张起每接到一张新牌就把它插到手里已有牌的正确位置保证左手里的牌始终是排好序的。这其实就是直接插入排序的行为。把这个过程翻译成数组操作我们把数组看成两个部分左边是已经排好序的部分右边是等待插入的部分。一开始第一个元素天然就是有序的因为只有一个元素不存在乱序问题。然后从第二个元素开始每次取一个待插入元素从右往左跟自己已经有序的部分逐个比较找到合适的落点插进去同时把那些比它大的元素往右挪一位给腾出位置来。这里要注意一个关键细节数组不像扑克牌不能真插到中间。数组的插入操作必须靠搬移实现——你找到落点之前得先把比待插元素大的元素挨个往后移动一格然后才能腾出那个位置把元素放进去。这个移动的成本正是插入排序在大量乱序数据上表现不佳的根本原因。2.2 完整过程推演用实际数组走一遍光讲概念容易飘我用一个具体数组手推一遍。假设数组是[5, 2, 4, 6, 1, 3]。第1轮从索引1开始待插入元素是2。左侧有序部分是[5]5 2所以把5右移一位数组变成[5, 5, 4, 6, 1, 3]然后把2放到索引0结果[2, 5, 4, 6, 1, 3]。前两个元素有序了。第2轮待插入元素是索引2的4。左侧有序部分是[2, 5]。5 4把5右移2 4停止落点就是索引1。数组变成[2, 4, 5, 6, 1, 3]。第3轮待插入元素是索引3的6。5 6直接不用移动有序部分变成[2, 4, 5, 6]。这个已经是最大的的情况是最好的一次比较就结束。第4轮待插入元素是索引4的1。它会一路比到底6 1右移5 1右移4 1右移2 1右移最后越出左边界落点是索引0。数组变成[1, 2, 4, 5, 6, 3]。注意当j一路减到-1的时候说明它是当前最小的一定要处理这个边界别写错。第5轮待插入元素是索引5的3。6 3右移5 3右移4 3右移然后2 3落点索引2。结果[1, 2, 3, 4, 5, 6]排序完成。通过这轮手推你能直观感受到一个元素要找到自己的位置比较次数和移动次数加起来大致等于它左边大于它的元素个数加1。在最坏情况逆序数组下每一轮都要从头比到尾比较和移动加起来大约会达到n的平方级别。2.3 代码实现与复杂度量化Java实现我给出一个最经典版本public static void insertionSort(int[] arr) { if (arr null || arr.length 1) { return; } // i指向当前待插入的元素从1开始因为索引0天然有序 for (int i 1; i arr.length; i) { int key arr[i]; int j i - 1; // 从右往左找插入位置同时把大于key的元素右移 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }这段代码你拿去面试手写完全没有问题。有几个点我想专门强调一下。第一为什么先用key arr[i]存起来因为后面循环搬移元素的时候arr[i]原来的值会被覆盖掉你不提前存等找到落点时原始值早就丢了。这属于指数级新手易错点。第二while的循环条件是arr[j] key。如果你写成会改变排序的稳定性。这一点我要详细说说。所谓稳定指相同值的元素在排序前和排序后的相对顺序保持不变。插入排序本来就是稳定的因为只有严格大于key的元素才会被右移过key的落点位置等于key的元素不会移动所以前面同值的元素保持在左边。一旦你把条件改成等于的元素也会被右移后面那个同值元素反而跑到前面去了稳定性就丢失了。很多场景里稳定性很重要比如按优先级排序后再按时间排序两次排序都不破坏之前的顺序靠的就是稳定排序。第三时间复杂度我做一张表给你情况比较次数移动次数时间复杂度最好数组已有序n-10O(n)最坏数组逆序n(n-1)/2n(n-1)/2O(n²)平均n(n-1)/4n(n-1)/4O(n²)这个表值得记一下很多人只知道最好O(n)最坏O(n²)但说不清为什么。最好情况每个元素只要和左边最近的那个比较一次就行所以比较n-1次一次移动都没有最坏情况每个元素都要挪到最左边第i个元素要比较i次、移动i次加起来就是等差数列求和公式1 2 ... (n-1) n(n-1)/2。空间复杂度就没什么好说的O(1)原地排序不依赖额外数组。2.4 插入排序的独特优势低常数与近乎有序场景我在前面提到插入排序的最坏复杂度是O(n²)这看起来不怎么样。但实际工程里它的地位远比你想象得高。原因就是常数因子和数据特征这两个层面。先谈常数。大O只是宏观趋势实际耗时等于操作次数 × 单次操作成本。插入排序的循环体里就是一次比较、一次赋值没有复杂的递归压栈、没有额外的缓存访问所以在数据量小于50的时候它往往能打赢快排和归并。我实测过纯Java环境下排序10万级别的随机整数插入排序确实惨不忍睹但排序50个随机整数Arrays.sort内部的Dual-Pivot QuickSort和手写插入排序差别很小甚至有些数据分布下插入排序更快因为它省去了递归和分区的开销。再说数据特征。插入排序对几乎有序的数据极其友好。比如一个数组只有个别位置错乱插入排序一轮比较下来基本不怎么搬移元素复杂度会线性退化到接近O(n)。这种特性在真实业务里非常常见数据库按主键插入了新记录、日志文件按时间新增了少量条目、排行榜偶尔修正几个分数……这些场景下直接调用O(n log n)的排序函数当然也没错但如果你能在局部用插入排序处理收益会非常明显尤其是在移动端和服务端性能敏感的位置。另外还有一个隐藏价值插入排序是很多高级排序算法的底座。经典的TimSort在归并阶段处理小分块、Introsort在递归深度过大时防止快排退化都会在小规模子序列上切换到插入排序。这背后就是工程上常说的杀鸡不用牛刀——复杂的算法在大数据上占优但在小数据上会被简单算法的低开销击败。理解了这个点你再看任何排序框架的源码会有一种哦原来这里的阈值是这个意思的顿悟。3. 希尔排序从挨个挪到跳着插的进化3.1 插入排序的痛点与希尔的核心破局点插入排序为什么慢因为它每一轮只能把元素挪一格。你想想如果最小的元素恰好排在最后面你为了把它送到数组最前面需要在每一轮里让它一点点往前移总共挪n-1次如果数据整体都是逆序那么总移动次数就累积成了n²规模。希尔排序的破局思路非常直白能不能让每个元素一开始就能跳着走比如隔开4个位置比较、移位让元素一下子跨过4个身位往前靠然后缩小间隔到2最后缩小到1让整个数组在最后一轮变成标准的插入排序。因为前面几轮已经做了预排序数组已经接近有序了最后一轮的插入排序效率极高。这个间隔在希尔排序里叫gap也叫增量。每一轮我们都把所有距离为gap的元素看作一组在组内做插入排序。随着gap不断缩小组越来越多、组内元素越来越少直到gap1变成普通的全数组插入排序。这个思路实现的难度其实不高但它蕴含的分治思想——先用大跨度粗调再用小跨度细调——在别的领域同样适用。3.2 增量序列希尔排序的性能密码你问十个懂希尔排序的人为什么要选这个gap序列可能八个答不上来。我在这里把它讲透。希尔排序的效率几乎完全取决于gap序列的选取。最原始的做法是gap不断减半先让gap n/2然后gap gap/2一路除到1。这个序列实现简单但它的最坏复杂度依然可能是O(n²)这一点很多人不知道。我给你举一个反直觉的例子当n是2的幂次时这种二分gap会让某些位置上的元素在整个排序过程中始终只在同奇偶性的位置上移动直到最后一轮gap1它们才可能发生跨奇偶的交换导致最后一步其实要处理相当大范围的逆序性能并不理想。后来有研究者在探索更优的增量序列。比如Hibbard序列取1, 3, 7, 15, ...也就是2^k - 1理论上最坏复杂度能压到O(n^1.5)Sedgewick序列取1, 5, 19, 41, 109, ...这种组合数序列最坏复杂度能到O(n^4/3)实际表现普遍认为更好。所以你在不同的教材里看到的希尔排序时间复杂度和代码选择有所不同很正常它们都在讲同一个算法、不同配置。那实际写代码怎么办我建议常规场景用最简单的gap/2序列因为实现清晰、不容易写错、测试验证简单。如果你遇到特定性能要求再去用Hibbard或Sedgewick序列。我个人在写工具脚本时也常这样处理当n 1000时二分gap的差距可以忽略当n上万、数据随机性强时换成Sedgewick序列耗时可能从十几毫秒降到几毫秒肉眼可见。3.3 完整推演一个例子看懂分组与插入的交织还是拿[5, 2, 4, 6, 1, 3]来数组长度n6。我们可以用gap3开始。gap3时数组被分成三组每组内元素按位置相差3来划分第一组是索引0和3即5和6第二组是索引1和4即2和1第三组是索引2和5即4和3。我们分别在每组内做插入排序第一组5和6已有序不变第二组2和1比较1更大还是2更大哦这里要注意第二组是2和1比较后1 2所以互换位置数组变成[5, 1, 4, 6, 2, 3]第三组4和33 4互换数组变成[5, 1, 3, 6, 2, 4]。然后gap1相当于全数组直接插入排序。数组现在是[5, 1, 3, 6, 2, 4]。这个数组不是完全有序的但相比原始[5, 2, 4, 6, 1, 3]较大的和较小的元素已经粗略分开了。最后一轮插入排序很快就把它变成[1, 2, 3, 4, 5, 6]。有人会问最后一轮不还是要处理6个元素吗没错但关键不在于处理的元素数量而在于每个元素要跨越的距离。经过前面的粗调最后一轮里每个元素离自己的目标位置已经比较近了插入排序的移动总量大幅下降所以总体耗时远小于直接对原始数组进行一次完整的插入排序。这就是希尔排序的精髓先付出少量成本把它调成近有序后面的插入排序就能享受近乎O(n)的待遇。3.4 希尔排序的代码实现与稳定性的致命短板演示完过程代码就好写了。我给出Java实现public static void shellSort(int[] arr) { int n arr.length; // 初始gap取n/2每次折半直到gap1 for (int gap n / 2; gap 0; gap / 2) { // 对每个gap分组在每个组内做插入排序 for (int i gap; i n; i) { int key arr[i]; int j i; // 在组内以gap为步长向左寻找插入位置 while (j gap arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } } }这段代码我最初学的时候看得很懵尤其是外层两个for循环为什么只需要两个嵌套不是应该三层循环分组、组内遍历、组内比较吗实际上这里做了一个很巧妙的合并i从gap开始遍历到n-1把不同组的元素交错着处理。i每增加1就相当于把当前元素往自己所属组的有序序列里插入。因为所有组的插入过程是交替进行的并不会互相干扰。这样做的好处是代码简洁而且只需要移动原数组不需要额外的辅助数组保存每组的数据。在写这段代码的时候最需要注意的细节是内层while的边界条件和步长j gap而不是j 0。因为比较时要用arr[j - gap]如果j小于gapj - gap就成负数了数组越界。一定要记得这个边界。我为什么用j - gap而不是j--因为当前元素是在自己那组里组内相邻元素的位置差是gap不是1。如果写成j--那比较的时候就会跨组比较了排序结果会错。这是我见过的最常见的希尔排序写错方式。还有一个重要特性必须强调希尔排序是不稳定的。为什么因为当gap大于1时相同值的元素可能被分到不同的组里某个值相同但下标不同的元素会在各自的组内移动跨越其他元素的相对位置导致同值元素的相对顺序在排序前后发生变化。这个特性在某种角度上有用如果你知道自己要处理的数据是数值且不需要保持任何次要顺序不稳定无所谓但如果数据是对象且依赖稳定性比如你之前按姓名排好序现在想按年龄排又希望同年龄的人依然按姓名排列那希尔排序就不合适。稳定性这个属性很多人觉得抽象我打个比方你就懂了。假设一班学生先按学号排好队现在想按身高重新排队如果排序算法稳定身高相同的同学会保持原来的学号顺序如果不稳定那身高相同的同学可能打乱顺序。数据库里多条件排序、分页查询、流式处理的中间结果往往都需要稳定排序来保证次级顺序不丢。所以做技术选型的时候先问自己一句我需要稳定吗4. 常见问题与排查技巧实录4.1 最容易翻车的5个细节代码能跑出来结果、但结果在边界情况上出错是这两个算法最常见的失败模式。我把自己这些年帮别人排查的典型问题整理成一个速查表问题现象常见原因解决办法插入排序数组越界while条件写成j 0导致第一个元素还没比较就被跳过条件应为j 0插入排序丢失元素忘记用key保存arr[i]被后面的搬移覆盖先int key arr[i]排序结果不稳定插入条件写成arr[j] key改成严格希尔排序分组混乱内层步长误写为j--步长必须是j - gap希尔排序最后一轮无效gap取整运算导致gap不是1循环条件gap 0确保gap最终到1这张表看起来简单但每一条我都见过不止一次。你说这些写错的人难道是能力不行吗不是大多是因为没想清楚这个变量到底指向什么位置这个元素的值在被覆盖前存没存下来这类基础问题。基础就是基础一个数组越界可能一整天都查不出来越早掌握这些边界意识越好。4.2 关于gap序列减半之外还有什么选择前面提到二分gap最坏能到O(n²)有人可能觉得不服难道减半序列真的那么差我得说它最坏情况确实是成立的只是触发条件比较苛刻。我在刷题网站遇到过这种数据数组长度恰好是2的幂但里面的元素顺序被故意构造使得所有奇偶位置分别各自逆序奇偶之间又交替穿插。这种情况下二分gap的预排序效果就很差几乎要把大量复杂度留到最后一步处理。如果对性能比较在意Sedgewick序列是一个不错的进阶选择。常见形式是取while (gap n) gap gap * 3 1这个gap序列从1开始一路生成1, 4, 13, 40, 121...然后排序时从大到小用。你也可以先生成最大的gap再不断缩小。实际测试中这个序列在中等规模数据上表现比减半更好。不过我提醒一句不要盲目追求所谓最佳序列很多论文里的理论最优序列用的是复杂的数学构造工程实现上收益并不大代码复杂度倒是上去了。够用就好是工程里更现实的态度。4.3 面试追问与实战败点为什么你的希尔排序跑不快招聘时我偶尔会追问希尔排序的复杂度。能说出平均大概O(n log n)和O(n²)之间、具体取决于gap的人我觉得是真正理解了的。但很多人会硬背一个希尔排序是O(n^1.3)之类的结论一听就是出来背书。这里我说一下我的理解理论复杂度确实有上界结果比如Hibbard序列能证明到O(n^1.5)Sedgewick序列能到O(n^4/3)但实际耗时还取决于你用什么增量、数据到底多乱、语言实现细节硬报一个精确数值反而容易露馅。面试里你如果能说出效率取决于增量序列没有统一结论工程上常用N/2序列理论优化常用Hibbard/Sedgewick序列这个回答的深度和可信度就立住了。再聊一个工程实战里容易踩的坑你写了个希尔排序类丢在工具包里面结果线上排序一跑耗时比直接调库函数还高被业务方质疑。这不是希尔排序本身的问题很可能是你的数据特征、阈值、增量选择全都不到位。我在一个并发任务调度的场景里就遇到过一份2000条左右的ID列表因为数据量小且已经大致有序我以为希尔排序会很快结果发现耗时反而不如库函数后来加了日志才看到那批数据的大致有序其实只体现在末尾几十条前面几百条完全是乱序的希尔排序的预排序反而多花了很多轮。后来我的处理方式是写一个简单的判断数据规模低于阈值直接用插入排序高于阈值的分类讨论而不是无脑套希尔。4.4 排序算法的对比选型什么时候别用希尔排序说实话希尔排序今天已经不是工业界的主力排序算法了。它更像一个承上启下的过渡角色向上承接简单插入排序向下启发快排、归并这类更复杂的分治排序。所以在实战选型时我的看法是这样的数据量小于50别犹豫直接插入排序就好。数据量在50到1000之间且内存紧张、不能用额外数组可以考虑希尔排序尤其是Sedgewick增量性价比不错。数据量破万且不在意稳定性优先用快速排序或Arrays.sort它们平均O(n log n)剪枝和优化做得很彻底手写很难超越。数据量大且要求稳定归并排序或TimSort是正确选择希尔排序直接排除。很多人会问快排那么强为什么还要学插入和希尔我的回答是排序算法是分层的高级算法内部也在用低级算法的思路做局部优化。你学了这两兄弟再看快排分区后对小数组使用插入排序的优化再看归并排序中对相邻有序区间的判断就再也看不出魔法感了全部是顺理成章。5. 扩展场景与最后几点心得两个排序算法讲完了。但我想顺带聊一点更宏观的因为在文章开头列出的那些热搜词里出现了字符串排序、数组排序、数据库排序、MapReduce排序等一堆实际场景。排序思想的应用远不止数组本身。比如数据库的ORDER BY背后涉及的不只是比较大小还有多字段的联合排序规则、NULL值的处理、大小写和中文排序规则。而MapReduce里的排序更核心的是分区-分组-二次排序这套机制同一Key的数据进入同一个ReducerReducer内部还需要按Value排序。你看这背后全是先按A排、再按B排的稳定排序思想插入排序的稳定性逻辑在这里一样适用。你要是理解了稳定性和增量排序再去看大数据框架的Shuffle过程会比别人快得多。再说字符串排序如果你只是用String.compareTo比字典序那是典型的逐字符比较复杂度取决于公共前缀长度但如果是大量字符串的排序LSD、MSD基数排序又会用按位稳定排序的思路其实就是反复执行稳定排序。你看基础排序算法永远是上层复杂系统的地基。最后说一点我的个人体会。我见过很多人刷了几百道算法题却依然写不好一个插入排序原因往往是没见过别人怎么错只顺着正确代码往下背。我建议你在写排序算法的日子里刻意写几个带坑的版本然后单步调试亲眼看到数组越界、亲手发现值被覆盖、亲身体验gap步长错乱带来的数据混乱。这个过程很笨但对建立算法直觉的帮助特别大。我自己带过的实习生里凡是肯花时间手动推演两三遍排序过程的人后面学快排、归并、堆排序都异常顺利而上来就背代码的人往往一到变体题就卡壳。如果你正在准备面试或者正在啃数据结构的教材可以再做一件事把这两个排序的代码用三种语言各写一遍Java、Python、C都行。语言切换会逼你把算法逻辑和语言语法分开这一步打通之后你会发现自己看排序源码的能力上了个台阶。这个内容后续还可以往排序稳定性实践快排与归并的分治思想常用库函数源码分析几个方向继续深挖而起始的那块基石永远就是我今天讲的这两个算法。