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

排序是数据结构里经常被人低估的一块内容。尤其直接插入排序和希尔排序，听起来都是入门课上的基础算法，背一背代码好像就完事了，但真正需要手写的时候，很多人才发现边界条件、循环变量、稳定性判断，每一个点都能让代码崩一次。我这些年自己写工具、帮人改代码、也带新人刷题，反复见过同样的问题，所以这篇就专门围绕这两个排序展开。文章会讲清楚它们各自的原理、手写实现、复杂度、稳定性，以及实际开发时到底怎么选，还会把我踩过的坑直接列出来。不管你是正在准备笔试、复习数据结构，还是想搞明白项目里该不该自己写排序，都可以照着走一遍。

1. 为什么排序这件事要从插入排序讲起

1.1 打牌时的直觉：把新牌插进已有序列

插入排序是排序算法里最贴近日常直觉的一种。想想打扑克的时候，大多数人摸到一张新牌，会习惯性地从右往左和手里的牌比较，找到合适的位置直接插进去。手里的牌始终是有序的，这个动作反复执行，整副牌就排好了。直接插入排序在数组里复现的正是这个动作：把数组的左边看成有序区，每一轮从右边未处理的区域取出第一个元素，向前找到合适的位置，把它插进有序区。

数组和链表不一样，链表中插入一个节点只需要改指针，数组里要在中间插入一个元素，就得把比它大的元素一个一个往右挪，腾出一个空位，再把目标元素放进去。所以直接插入排序看起来简单，实际代码里包含两个动作：找位置、腾空位。更巧妙的是，在数组的实现中找位置和腾空位是同步进行的——从后往前一边比较一边移动，而不是先完整地扫描一遍找到位置，再进行第二轮移动。

这个算法的思路也叫“增量式构造有序区”。它不依赖额外空间，所有的操作都在原数组上完成，空间复杂度是 O(1)。对于新手来说，它是一个非常友好的起点，因为理解了直接插入排序，后面再学希尔排序几乎是一层窗户纸的事。

1.2 有序区、无序区和循环不变量

如果只看代码，插入排序不过几行，但要说清楚“它为什么是对的”，就需要一点理论工具。很多教科书和算法导论（包括 CLRS）里会用到“循环不变量”这个概念，听起来高大上，其实说人话就是：每一轮循环开始前和结束后，都有某个性质始终不变。

对直接插入排序来说，这个性质是：在处理第 i 个元素之前，前 i 个元素已经是有序的，而且它们就是原数组前 i 个元素的集合。第 i 轮要做的事情，就是把当前这个元素插入到前面有序区中的正确位置。循环结束后，前 i+1 个元素保持有序，于是当 i 一路走到 n-1，整个数组自然就有序了。

面试时如果被问到“怎么证明插入排序是对的”，用循环不变量的框架回答，比背代码强太多。它还能顺手解释为什么外层循环可以从 1 开始：因为单元素数组天然有序，arr[0] 自己就构成初始的有序区。这也顺带处理了 n=0 或 n=1 的边界情况，外层循环体根本不会执行。

1.3 直接插入排序的复杂度特征

直接插入排序的时间复杂度受数据初始排列影响很大，这一点和很多排序算法都不一样。

最好情况是原序列已经有序。每轮只需要把当前元素和前一个元素比较一次，发现顺序正确就继续，不需要移动任何元素。这样总共做 n-1 次比较，时间复杂度是 O(n)。

最坏情况是原序列完全逆序。每一轮的当前元素都要一路挪到最前面，比较次数和移动次数都会达到 n(n-1)/2 的量级，所以时间复杂度是 O(n^2)。

平均情况也是 O(n^2)，因为随机排列下每个元素平均要移动大约三分之一到四分之一长度的距离，整体仍然是平方级。但要注意，这个平方级的系数很小，尤其当数据量小、数据基本有序时，它的实际速度并不输给很多 O(n log n) 的算法。

还有一个非常重要的结论：直接插入排序是稳定排序。这里的“稳定”指的是，在序列中存在相同元素时，排序后它们的相对顺序不会改变。这个性质在真实场景里很值钱，后面我会单独展开说。

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] = key

Python 新手更容易写出一种“相邻交换”版本的插入排序：用双层循环，从 i 往前冒泡式交换相邻元素。这样写也能排序，但每次“交换”需要三次赋值，而用 key 暂存加右移的写法只需要一次赋值完成移动，最后再写回 key。两者常数差距在数据量稍大时会被放大。

另外提醒一句，如果你想要一个返回新列表的版本，记得先复制传入的数组，否则直接遍历原列表会影响外面看到的数据。

2.3 用 [5, 2, 4, 6, 1, 3] 模拟每一趟

只看代码不够直观，我拿一个小数组完整走一遍。初始数组：

[5, 2, 4, 6, 1, 3]

第 1 轮，i=1，key=2。从 j=0 开始比较，5 大于 2，把 5 右移到下标 1，j 变成 -1。循环退出，key 放到下标 0。数组变成：

[2, 5, 4, 6, 1, 3]

第 2 轮，i=2，key=4。5 大于 4，右移到下标 2；j=0 时 2 不大于 4，停下。key 放到下标 1。数组变成：

[2, 4, 5, 6, 1, 3]

第 3 轮，i=3，key=6。前面 5 不大于 6，不用移动。数组不变：

[2, 4, 5, 6, 1, 3]

第 4 轮，i=4，key=1。这是最累的一轮，从后往前，6、5、4、2 依次右移，key 最后放到下标 0。数组变成：

[1, 2, 4, 5, 6, 3]

第 5 轮，i=5，key=3。6 和 5 都往右移一位，到 j=1 时发现 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) 级别、适合小数据量的简单排序，但细节差异很大。

选择排序每轮只做一次交换，交换次数少，但比较次数是固定的，不会因为数据接近有序而减少。它最吃亏的地方在于不稳定：选择排序会把一个较小元素换到前面，可能越过另一个与它相等的元素，导致相对顺序改变。

冒泡排序虽然是稳定的，但每轮冒泡都要做大量相邻交换，常数比插入排序大。工程上很少有人在非教学场景里首选冒泡排序。

直接插入排序的独特优势是“数据越接近有序，跑得越快”。如果输入基本有序，它几乎只需要扫描一遍就能完成；选择排序遇到基本有序的数据，还得老老实实比较 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，再分组、再排序；重复直到 gap=1。

最后一轮 gap=1 的时候，它就是一个普通直接插入排序。但由于前面几轮已经让大数大致集中在右侧、小数大致集中在左侧，最后一轮需要移动的元素非常少，所以整体代价远小于直接插入排序最坏情况。

工程实现的写法通常不是“先完整排序第一组，再排序第二组”，而是让 i 从 gap 开始遍历到 n-1，对每个元素，把它插入到它所在分组的前面正确位置。这两种写法最终结果等价，但后面这种代码更短，不用维护不同分组的起点，缓存访问也更均匀。

需要特别记住的是，前面的多轮分组插入并不会真正把整个数组排好，它的目标是“大致有序”。最后一轮 gap=1 必须执行，否则排序不完整。

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/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]

第一轮，gap=4。按间隔 4 分组，索引情况是：

• 索引 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 只经过一次插入就跳到了最前面，9 被推到了最后面附近。这就是跳跃式移动的威力。

第二轮，gap=2。这相当于把下标为偶数的所有元素当成一组，把下标为奇数的所有元素当成另一组，分别做插入排序。

• 偶数下标组：1, 3, 5, 7, 9，已经有序，不需要移动。
• 奇数下标组：4, 2, 8, 6，插入排序后变成 2, 4, 6, 8。

第二轮结束后，数组变成：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

第三轮，gap=1，就是普通直接插入排序。算法仍会从头扫一遍，但因为数组已经整体有序，它只需逐个和后一个元素比较一次，发现不需要移动，很快结束。

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 初始值算错，或者循环变量更新写错，导致跳过 gap=1。这样最后一轮没有执行完整插入排序，整个数组不会有序，而且很多小规模测试里可能看不出来，因为前面的分组恰好让数据看起来差不多了。

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 永远不变，陷入死循环。这类问题调试起来很痛苦，因为代码看起来就一行的问题。

第五，对空数组和单元素数组没做保护。虽然很多实现天然能处理 n=0，但希尔排序里要计算初始 gap，如果 n 很小，gap 可能直接变成 0，外层循环就错过了最后一步。函数入口处统一加一个if (n <= 1) return;，成本最低。

6.3 工程上什么时候该用现成排序

这是我特别想对新人说的一点：日常业务开发里，不要轻易自己手写排序。

Java 里有Arrays.sort和Collections.sort，C++ 里有std::sort和std::stable_sort，Python 里有list.sort和sorted，JavaScript 里也有原生Array.prototype.sort。这些实现经历过无数次性能优化和边界测试，在稳定性、大数据量、并发安全上都比自己写的可靠得多。数据库里的ORDER BY，无论是 MySQL 还是其他数据库，查询引擎都有成熟的排序器，不需要你去读出来排完再写回去。前端点击表头排序、后端接口里按字段排序，也都是调用现成能力。

但自己会写排序算法，仍然不是一个可有可无的技能。笔试面试、嵌入式开发、算法库底层、教学研究，还有当你确实需要定制排序规则时，比如按中文字符串的本地化顺序排序、按对象多字段组合排序，你都得更深入地理解底层算法才能改得放心。

我在实际开发里的习惯是：第一选择永远是库函数。真到了需要手写的时候，插入排序负责小数据和基本有序场景，希尔排序负责小规模且逆序度高的场景，快速排序和归并排序负责大数据量。理解这几个算法的边界，比背代码重要得多。

最后分享一个小技巧。我练排序算法时，会把直接插入排序当成一切排序的入口：先默写插排，再把间隔改成 gap 变成希尔排序，然后随机生成几千个数组自测。手写代码能一次跑对，逻辑基本就过关了。以后再见到什么花哨的排序算法，你也能站在“局部有序区怎么扩大”的角度去理解，而不是被一堆复杂操作带偏。