直接插入排序与希尔排序：原理、手写实现与工程选型

排序是数据结构里经常被人低估的一块内容。尤其直接插入排序和希尔排序听起来都是入门课上的基础算法背一背代码好像就完事了但真正需要手写的时候很多人才发现边界条件、循环变量、稳定性判断每一个点都能让代码崩一次。我这些年自己写工具、帮人改代码、也带新人刷题反复见过同样的问题所以这篇就专门围绕这两个排序展开。文章会讲清楚它们各自的原理、手写实现、复杂度、稳定性以及实际开发时到底怎么选还会把我踩过的坑直接列出来。不管你是正在准备笔试、复习数据结构还是想搞明白项目里该不该自己写排序都可以照着走一遍。1. 为什么排序这件事要从插入排序讲起1.1 打牌时的直觉把新牌插进已有序列插入排序是排序算法里最贴近日常直觉的一种。想想打扑克的时候大多数人摸到一张新牌会习惯性地从右往左和手里的牌比较找到合适的位置直接插进去。手里的牌始终是有序的这个动作反复执行整副牌就排好了。直接插入排序在数组里复现的正是这个动作把数组的左边看成有序区每一轮从右边未处理的区域取出第一个元素向前找到合适的位置把它插进有序区。数组和链表不一样链表中插入一个节点只需要改指针数组里要在中间插入一个元素就得把比它大的元素一个一个往右挪腾出一个空位再把目标元素放进去。所以直接插入排序看起来简单实际代码里包含两个动作找位置、腾空位。更巧妙的是在数组的实现中找位置和腾空位是同步进行的——从后往前一边比较一边移动而不是先完整地扫描一遍找到位置再进行第二轮移动。这个算法的思路也叫“增量式构造有序区”。它不依赖额外空间所有的操作都在原数组上完成空间复杂度是 O(1)。对于新手来说它是一个非常友好的起点因为理解了直接插入排序后面再学希尔排序几乎是一层窗户纸的事。1.2 有序区、无序区和循环不变量如果只看代码插入排序不过几行但要说清楚“它为什么是对的”就需要一点理论工具。很多教科书和算法导论包括 CLRS里会用到“循环不变量”这个概念听起来高大上其实说人话就是每一轮循环开始前和结束后都有某个性质始终不变。对直接插入排序来说这个性质是在处理第 i 个元素之前前 i 个元素已经是有序的而且它们就是原数组前 i 个元素的集合。第 i 轮要做的事情就是把当前这个元素插入到前面有序区中的正确位置。循环结束后前 i1 个元素保持有序于是当 i 一路走到 n-1整个数组自然就有序了。面试时如果被问到“怎么证明插入排序是对的”用循环不变量的框架回答比背代码强太多。它还能顺手解释为什么外层循环可以从 1 开始因为单元素数组天然有序arr[0] 自己就构成初始的有序区。这也顺带处理了 n0 或 n1 的边界情况外层循环体根本不会执行。1.3 直接插入排序的复杂度特征直接插入排序的时间复杂度受数据初始排列影响很大这一点和很多排序算法都不一样。最好情况是原序列已经有序。每轮只需要把当前元素和前一个元素比较一次发现顺序正确就继续不需要移动任何元素。这样总共做 n-1 次比较时间复杂度是 O(n)。最坏情况是原序列完全逆序。每一轮的当前元素都要一路挪到最前面比较次数和移动次数都会达到 n(n-1)/2 的量级所以时间复杂度是 O(n^2)。平均情况也是 O(n^2)因为随机排列下每个元素平均要移动大约三分之一到四分之一长度的距离整体仍然是平方级。但要注意这个平方级的系数很小尤其当数据量小、数据基本有序时它的实际速度并不输给很多 O(n log n) 的算法。情况比较次数移动次数时间复杂度最好已经有序n-10O(n)最坏完全逆序n(n-1)/2n(n-1)/2O(n^2)平均随机排列约 n^2/4约 n^2/4O(n^2)还有一个非常重要的结论直接插入排序是稳定排序。这里的“稳定”指的是在序列中存在相同元素时排序后它们的相对顺序不会改变。这个性质在真实场景里很值钱后面我会单独展开说。2. 直接插入排序的手写实现与逐趟走查2.1 最稳妥的 C 语言写法不管面试还是项目里临时手写我最推荐的直接插入排序写法是这样的void insertion_sort(int arr[], int n) { if (n 1) return; for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }这里几个细节值得反复看。第一key arr[i]必须先保存当前要插入的元素因为后面的循环会把 arr[i] 原来的位置覆盖掉。丢了 key后面就无从插入了。第二while (j 0 arr[j] key)这个条件里j 0是最容易写漏的。一旦遗漏在 C 语言里就可能读出数组边界外的随机内存程序不一定会崩但排序结果一定是错的。这种 bug 在调试时非常隐蔽。第三循环退出时arr[j]是第一个不大于 key 的元素所以 key 要放到arr[j 1]。如果你写成了arr[j] key就会把有序区里的一个元素覆盖掉这是新手最常犯的错误。第四判断条件用的是而不是。这是保持稳定性的关键。相等元素不移动相对顺序就不会被打乱。我见过有的人喜欢给这类排序函数加一个if (n 1) return;保护。其实不加也不会有问题因为外层循环从 1 开始。但加了能让边界情况更明确尤其当函数是被外部调用时空数组和单元素数组是真实存在的输入早做处理没有坏处。2.2 Java 与 Python 实现中的注意点Java 的数组作为参数传入方法时方法里直接修改的是数组里的元素所以排序是原地生效的不需要返回值。public static void insertionSort(int[] arr) { for (int i 1; i arr.length; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }Python 写起来也差不多。列表是可变对象传入函数后直接改就能看到效果。def insertion_sort(arr): for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] keyPython 新手更容易写出一种“相邻交换”版本的插入排序用双层循环从 i 往前冒泡式交换相邻元素。这样写也能排序但每次“交换”需要三次赋值而用 key 暂存加右移的写法只需要一次赋值完成移动最后再写回 key。两者常数差距在数据量稍大时会被放大。另外提醒一句如果你想要一个返回新列表的版本记得先复制传入的数组否则直接遍历原列表会影响外面看到的数据。2.3 用 [5, 2, 4, 6, 1, 3] 模拟每一趟只看代码不够直观我拿一个小数组完整走一遍。初始数组[5, 2, 4, 6, 1, 3]第 1 轮i1key2。从 j0 开始比较5 大于 2把 5 右移到下标 1j 变成 -1。循环退出key 放到下标 0。数组变成[2, 5, 4, 6, 1, 3]第 2 轮i2key4。5 大于 4右移到下标 2j0 时 2 不大于 4停下。key 放到下标 1。数组变成[2, 4, 5, 6, 1, 3]第 3 轮i3key6。前面 5 不大于 6不用移动。数组不变[2, 4, 5, 6, 1, 3]第 4 轮i4key1。这是最累的一轮从后往前6、5、4、2 依次右移key 最后放到下标 0。数组变成[1, 2, 4, 5, 6, 3]第 5 轮i5key3。6 和 5 都往右移一位到 j1 时发现 2 不大于 3停下。key 放到下标 2。数组变成[1, 2, 3, 4, 5, 6]这个例子可以看到一个规律每一轮结束左边有序区的长度就增加 1。整个过程中只有第 4 轮付出了比较大的移动代价这也是为什么完全逆序的数组会让直接插入排序很吃力。3. 稳定性、选择排序对比与适合它的真实场景3.1 稳定性的意义和插入排序为什么天然稳定稳定排序的定义是如果序列中有关键字相等的元素排序后它们的相对顺序保持不变。举个例子一组学生记录先按姓名字母排好序然后要求再按年龄排序。如果排序算法是稳定的那么年龄相同的学生仍然保持姓名字母顺序如果算法不稳定年龄相同的学生顺序可能会乱掉。这个场景在真实产品里太常见了。桌面表格“点击表头排序”、前端数据表格的多列排序后台管理系统的二次排序依赖的都可能是稳定性。很多框架在对一组对象先按某个字段排序后再按另一个字段排序时会隐式依赖上一次排序的相对顺序这时用到稳定排序就能省去很多额外逻辑。直接插入排序为什么稳定因为内层循环的判断条件里只有当前一个元素“大于”key 时才移动它。两个相等元素的 key 不会触发移动所以它们在顺序上不会交错。反过来如果我把条件写成了arr[j] key相等元素也会向右移排序结果虽然大体有序稳定性却被破坏了。这也是为什么我一直强调手写代码时要严格区分和。3.2 与选择排序、冒泡排序的对比很多人会把直接插入排序、选择排序、冒泡排序放在一起比较因为它们都属于 O(n^2) 级别、适合小数据量的简单排序但细节差异很大。排序最好平均最坏稳定性主要开销直接插入排序O(n)O(n^2)O(n^2)稳定元素移动选择排序O(n^2)O(n^2)O(n^2)不稳定元素比较冒泡排序O(n)O(n^2)O(n^2)稳定元素交换选择排序每轮只做一次交换交换次数少但比较次数是固定的不会因为数据接近有序而减少。它最吃亏的地方在于不稳定选择排序会把一个较小元素换到前面可能越过另一个与它相等的元素导致相对顺序改变。冒泡排序虽然是稳定的但每轮冒泡都要做大量相邻交换常数比插入排序大。工程上很少有人在非教学场景里首选冒泡排序。直接插入排序的独特优势是“数据越接近有序跑得越快”。如果输入基本有序它几乎只需要扫描一遍就能完成选择排序遇到基本有序的数据还得老老实实比较 n(n-1)/2 次完全享受不到这个红利。3.3 现实中哪些地方会用到插入排序很多同学觉得插入排序只是考试题实际项目里根本轮不到。其实它是很多工业级排序库的底座。最典型的是快速排序的实现。快排在递归分区到很小尺寸时比如剩余元素少于 16 个或 32 个很多实现会直接切换成直接插入排序。原因是小数组上插入排序的常数非常小而快速排序继续递归的开销反而更大。Java 的Arrays.sort、Python 的 TimSort、以及不少 C 语言的标准库实现都采用了这套“大区间快排/小区间插入”的组合策略。链表排序也经常用插入排序。链表不像数组需要腾挪元素插入一个新节点只需要改指针所以直接插入排序在有序链表上写起来很简洁维护成本低。再比如嵌入式或驱动环境里没有现成的标准库排序可用C 语言里手写一个直接插入排序就是最可靠、最不容易出问题的选择。数据量不大时它的性能完全够用。4. 希尔排序从“插队”到“跳着插队”4.1 每次只移动一步的瓶颈到底在哪直接插入排序最大的痛点是元素每次只能移动一个位置。这个限制在完全逆序的数据里尤其致命最后一个很小的元素想到最前面去得一步一步挪过前面所有元素移动代价接近 n 的平方。想象一下数组[9, 8, 7, 6, 5, 4, 3, 2, 1]直接插入排序会把 1 从最后一个位置一路挪到第一个位置期间 9、8、7、6、5、4、3、2 全都要右移一遍。如果能打破“只能相邻移动”的限制让元素跳着走前期做几次大跨度调整后面再做精细插入效率就会明显提升。希尔排序干的就是这件事。4.2 分组插入的核心思想希尔排序的基本思路可以用一句话概括按间隔 gap 把数组拆成若干子序列对每个子序列分别做插入排序然后缩小 gap再分组、再排序重复直到 gap1。最后一轮 gap1 的时候它就是一个普通直接插入排序。但由于前面几轮已经让大数大致集中在右侧、小数大致集中在左侧最后一轮需要移动的元素非常少所以整体代价远小于直接插入排序最坏情况。工程实现的写法通常不是“先完整排序第一组再排序第二组”而是让 i 从 gap 开始遍历到 n-1对每个元素把它插入到它所在分组的前面正确位置。这两种写法最终结果等价但后面这种代码更短不用维护不同分组的起点缓存访问也更均匀。需要特别记住的是前面的多轮分组插入并不会真正把整个数组排好它的目标是“大致有序”。最后一轮 gap1 必须执行否则排序不完整。4.3 步长序列怎么选gap/2、Knuth、Sedgewick步长序列是希尔排序的灵魂。不同步长带来的性能差异可能很大。最简单、应用最广的递减策略是初始gap n / 2之后每次gap gap / 2也就是对半分。这个序列代码最短面试中一般够用但性能不是最优的某些特殊输入下最坏情况会退化到 O(n^2)。比较经典的改进是 Knuth 序列。可以先找一个小于 n 的初始 gap然后每次按gap gap / 3递减int gap 1; while (gap n / 3) { gap gap * 3 1; }这样生成的序列是 1, 4, 13, 40, 121……比单纯对半分的跳跃感更强平均性能更好。再往上还有 Sedgewick 序列等更复杂的步长设计它们可以在理论上把希尔排序的最坏复杂度改进到 O(n^(4/3)) 甚至更好但日常工程中很少需要到这个程度。步长序列递推方式典型表现对半分 gap/2n/2, n/4, …, 1代码简单最坏 O(n^2)Knuthgap gap*31递减时 gap/3实现不算复杂工程推荐Sedgewick混合序列理论性能更好实现复杂少用我的建议是笔试手撕用 gap/2 完全没问题真要写工具或对性能有要求时换成 Knuth 序列改动只有几行收益却很实在。5. 希尔排序手写实现与完整走查5.1 标准写法与常见写法辨析先给一个以 gap/2 为基础的 C 语言实现void shell_sort(int arr[], int n) { for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key arr[i]; int j i; while (j - gap 0 arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } } }初次看到这段代码最容易困惑的是内层循环为什么和直接插入排序长得不完全一样。对比一下直接插入排序j i - 1比较arr[j]最后写入arr[j 1]。希尔排序j i比较arr[j - gap]最后写入arr[j]。这两种形式本质上是一回事只是希尔排序的间隔从 1 变成了 gap。我用“当前空位”来理解一开始key 从 arr[i] 里被抽走所以下标 i 是空位如果前面间隔 gap 的元素比 key 大就把它搬到空位空位前移 gap最后把 key 放进空位。这样理解起来代码就顺了。Python 版本用同样的逻辑def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): key arr[i] j i while j gap and arr[j - gap] key: arr[j] arr[j - gap] j - gap arr[j] key gap // 2如果把外层步长换成 Knuth 序列C 代码可以这样改int gap 1; while (gap n / 3) { gap gap * 3 1; } for (; gap 0; gap / 3) { // 内层逻辑同上 }5.2 用 [9, 8, 7, 6, 5, 4, 3, 2, 1] 走完全过程拿一个最极端的逆序数组来走查最能体现希尔排序的优势。初始数组[9, 8, 7, 6, 5, 4, 3, 2, 1]第一轮gap4。按间隔 4 分组索引情况是索引 0、4、89, 5, 1插入排序后变成 1, 5, 9索引 1、58, 4插入排序后变成 4, 8索引 2、67, 3插入排序后变成 3, 7索引 3、76, 2插入排序后变成 2, 6这一轮结束后数组变成[1, 4, 3, 2, 5, 8, 7, 6, 9]注意1 只经过一次插入就跳到了最前面9 被推到了最后面附近。这就是跳跃式移动的威力。第二轮gap2。这相当于把下标为偶数的所有元素当成一组把下标为奇数的所有元素当成另一组分别做插入排序。偶数下标组1, 3, 5, 7, 9已经有序不需要移动。奇数下标组4, 2, 8, 6插入排序后变成 2, 4, 6, 8。第二轮结束后数组变成[1, 2, 3, 4, 5, 6, 7, 8, 9]第三轮gap1就是普通直接插入排序。算法仍会从头扫一遍但因为数组已经整体有序它只需逐个和后一个元素比较一次发现不需要移动很快结束。轮次gap操作内容结束后的数组初始--[9, 8, 7, 6, 5, 4, 3, 2, 1]第一轮4按间隔 4 分成 4 组分别插入排序[1, 4, 3, 2, 5, 8, 7, 6, 9]第二轮2偶下标组和奇下标组分别插入排序[1, 2, 3, 4, 5, 6, 7, 8, 9]第三轮1普通插入排序基本无需移动[1, 2, 3, 4, 5, 6, 7, 8, 9]5.3 希尔排序的稳定性、复杂度与隐藏陷阱这里要说一个容易被忽略的点希尔排序是不稳定的。虽然希尔排序内部用的也是插入排序而插入排序本身稳定但希尔排序引入了多个不同间隔的分组过程。相等元素可能被分到不同组也可能在某一轮大跨度移动时越过另一个相等元素导致最终相对顺序发生变化。所以如果你明确需要一个稳定排序不要用希尔排序直接选归并排序或插入排序更稳妥。复杂度方面希尔排序到底多快取决于步长序列。gap/2 序列在某些特殊输入下最坏仍是 O(n^2)Knuth 序列的典型复杂度约在 O(n^(3/2)) 左右更复杂的步长序列还能做得更好。这也是希尔排序被称为“说不清复杂度”的算法的原因——它不是单一定义的算法而是一族以插入排序为基础的算法。写代码时有两个高频陷阱一个是while (j - gap 0)写成while (j 0)然后继续访问arr[j - gap]。在 C 语言里会出现数组越界在 Python 里会变成负索引倒序访问不报错但结果全错。这种问题靠肉眼可能很难发现建议写完代码后用随机数组多测几轮。另一个是外层循环没有让 gap 递减到 1。比如 gap 初始值算错或者循环变量更新写错导致跳过 gap1。这样最后一轮没有执行完整插入排序整个数组不会有序而且很多小规模测试里可能看不出来因为前面的分组恰好让数据看起来差不多了。6. 实测经验、常见坑和工程选型建议6.1 数据量多小的时候可以无脑用插入排序我自己的实测经验是在普通 PC 上数据量只有几千甚至一两万时直接插入排序的实测速度经常不输给 O(n log n) 的排序算法。尤其当数据接近有序、或只有少量乱序时插入排序的优势非常明显因为它几乎只是在做一遍遍历确认。快速排序虽然平均复杂度更低但递归调用、分区交换都有不小的常数开销。插入排序的循环体只有简单比较和赋值函数调用栈也浅所以小数组上它反而是最快的选择之一。这也是很多标准库在快排分区小于 16 到 32 时就切到插入排序的原因。如果你在工作中自己实现排序工具把“插入排序切换阈值”定在 16 或 32通常是比较稳妥的。希尔排序则更适合小到中等规模、且无法确定数据是否接近有序的场景。它代码量小、不需要额外栈空间在嵌入式环境里比递归版的快速排序更友好。如果数据量已经大到几十万以上我更倾向直接上快速排序、归并排序或调用库函数不要把希尔排序当万能解。6.2 手写排序最容易犯的五个错误这些错误我见过太多次列出来可以帮你少踩几个坑。第一数组越界。插入排序内层循环忘记判断j 0希尔排序忘记判断j - gap 0。在 C 语言里越界非常隐蔽程序不一定崩但结果会莫名其妙地错。第二稳定性判断失控。把arr[j] key写成arr[j] key导致相等元素被移动。普通排序看不出大问题但稳定排序场景里就是 bug。写代码时要想清楚你到底是“严格大于才动”还是“大于等于都动”。第三哨兵位用得不熟。有人喜欢在数组前面留一个哨兵位把 key 提前放到哨兵位置省去j 0的判断。这个技巧本身没问题但前提是哨兵的最大值小于所有待排序数据否则哨兵失去作用。如果不熟练别为了炫技而用哨兵老老实实写越界判断更稳。第四希尔排序的 gap 更新错误。比如gap初始为 1外层直接跳过或者gap / 2写成了gap / 2导致 gap 永远不变陷入死循环。这类问题调试起来很痛苦因为代码看起来就一行的问题。第五对空数组和单元素数组没做保护。虽然很多实现天然能处理 n0但希尔排序里要计算初始 gap如果 n 很小gap 可能直接变成 0外层循环就错过了最后一步。函数入口处统一加一个if (n 1) return;成本最低。6.3 工程上什么时候该用现成排序这是我特别想对新人说的一点日常业务开发里不要轻易自己手写排序。Java 里有Arrays.sort和Collections.sortC 里有std::sort和std::stable_sortPython 里有list.sort和sortedJavaScript 里也有原生Array.prototype.sort。这些实现经历过无数次性能优化和边界测试在稳定性、大数据量、并发安全上都比自己写的可靠得多。数据库里的ORDER BY无论是 MySQL 还是其他数据库查询引擎都有成熟的排序器不需要你去读出来排完再写回去。前端点击表头排序、后端接口里按字段排序也都是调用现成能力。但自己会写排序算法仍然不是一个可有可无的技能。笔试面试、嵌入式开发、算法库底层、教学研究还有当你确实需要定制排序规则时比如按中文字符串的本地化顺序排序、按对象多字段组合排序你都得更深入地理解底层算法才能改得放心。我在实际开发里的习惯是第一选择永远是库函数。真到了需要手写的时候插入排序负责小数据和基本有序场景希尔排序负责小规模且逆序度高的场景快速排序和归并排序负责大数据量。理解这几个算法的边界比背代码重要得多。最后分享一个小技巧。我练排序算法时会把直接插入排序当成一切排序的入口先默写插排再把间隔改成 gap 变成希尔排序然后随机生成几千个数组自测。手写代码能一次跑对逻辑基本就过关了。以后再见到什么花哨的排序算法你也能站在“局部有序区怎么扩大”的角度去理解而不是被一堆复杂操作带偏。