从插入排序到希尔排序：Python实现与优化全解析

说到排序算法插入排序可能是最被低估的一个。绝大多数人学它只是因为“简单”花五分钟看完就丢到一边然后急着去啃快排、归并这些更“高级”的算法。但你要是真把它吃透就会发现这个算法的优化思路几乎串起了排序算法演进的半条主线从最朴素的交换版本到移位版本再到二分插入排序最后一路进化出希尔排序。我这次就把这条线完整串一遍用 Python 从零写起每一步优化都配上实测对比和适用场景分析把插入排序为什么值得重新研究这件事聊透。这篇文章适合三类人看一是刚学排序算法、想把基础打扎实的初学者二是面试前想系统梳理排序算法细节的人三是在实际项目中纠结“小数组到底用哪种排序”的开发者。我会尽量把每一版代码、每一次优化的逻辑讲清楚不只给结论更给推导过程。1. 插入排序的直觉来源整理扑克牌就是最好的老师如果你打过扑克牌其实早就掌握插入排序的核心思想了。摸牌的时候大多数人会习惯性地把新摸到的牌插入到手里已有牌堆的合适位置让整副牌始终保持从左到右递增的顺序。这个过程没有额外扫描整副牌只是把当前这张牌跟前面挨着的牌依次比较找到位置后插进去。插入排序就是把这套动作原封不动搬到数组上。形式上插入排序把数组逻辑上分成两部分左边是“已经排好序的部分”右边是“尚未处理的部分”。每一轮循环取出右边部分的第一个元素然后从右往左扫描左边的有序区找到它应该在的位置并插进去。扫描的次数取决于这个元素比左边多少个元素小。有个细节值得先想清楚为什么直接从第二个元素开始而不是从第一个因为单个元素天然就是有序的——把一个元素的数组拿给任何人看它都已经排好了。所以算法从下标 1 开始把第二个元素当作第一张待插入的牌。说到这你可能觉得就这这不就是个双重循环暴力比较吗没错但暴力也有暴力的讲究。插入排序的暴力是“聪明的暴力”它每一轮的扫描范围永远只到正确位置为止而不是无脑扫完整个数组。数组越接近有序扫描次数就越少最好情况下甚至退化成线性时间。这个特性是后面所有优化的理论根基也是三种优化方向共同的出发点。2. 第一版实现先跑通再谈优化交换版与移位版的区别写代码之前先明确一个常见困惑数组不像链表插入一个元素需要把该位置原有元素全部后移这是插入排序成本的大头。初学者最容易写出的版本是“冒泡式交换”——发现逆序就交换相邻两个数一路把当前元素“泡”到前面。代码如下def insertion_sort_swap(arr): n len(arr) for i in range(1, n): j i while j 0 and arr[j] arr[j - 1]: arr[j], arr[j - 1] arr[j - 1], arr[j] j - 1 return arr这个版本逻辑上很好懂每一轮把当前元素往左“冒泡”直到它前面没有比自己大的元素为止。但整段代码里隐藏着一个问题——每交换一次要做三次赋值操作而且 Python 里arr[j], arr[j-1] arr[j-1], arr[j]实际上会创建临时元组开销比普通赋值更大。如果一组元素要移动 k 位交换版会做 3k 次赋值而这里面其实有大量重复劳动。更快的是经典的移位版本。思路变成先取当前元素作为临时版本“暂存”然后一步步把前面较大的元素往右挪腾出位置最后把暂存的元素放进空出来的位置。三趟赋值被压缩成一次暂存加上 k 次单赋值最后再一次赋值回位总共 k2 次赋值。代码长这样def insertion_sort_shift(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 return arr注意while循环结束后的arr[j 1] key。很多第一次写的人容易在这里搞错下标——写成arr[j] key结果丢失元素。别问我是怎么知道的。这里逻辑是循环退出的原因有两个要么 j 已经等于 -1说明前面所有元素都比 key 大key 应该放在数组头部要么 arr[j] key说明 key 应该插入到 arr[j] 的后面两种情况都对应下标 j 1。两个版本的时间复杂度都是 O(n²)但实际跑起来差距肉眼可见。我在一台普通笔记本上对 5000 个随机数做了测试交换版平均耗时约 118 毫秒移位版约 72 毫秒差距接近 40%。对于算法进阶来说这种优化属于“常数级别”的优化不改变量级但是在数据量几万几十万时差距会进一步放大。而且 Python 里元组交换的开销比 C 语言大得多所以在用 Python 写排序时这种细微差别会被进一步放大这也是为什么 Python 场景下更值得注意这种写法的差异。3. 第一次优化移位代替交换赋值次数才是真正的账上一节的两种写法其实已经隐含了第一次优化的结论但我想单独拉出来聊一聊因为很多人只记住了“移位版更快”却说不出为什么。这里把账算清楚。一次交换arr[j], arr[j-1] arr[j-1], arr[j]的成本包含读取两个元素的值、构造元组、写回两个元素。严格来说 Python 的字节码执行层面一条多重赋值会被拆成多条指令。而一次移位arr[j1] arr[j]就是纯粹的一次读取加一次写入。当某个元素需要向左移动 k 个位置时交换版做 k 次交换每次 3 次赋值暂存一个值、两个写回实际上 Python 内部是 ROT_TWO 机制但无论如何开销 1 次赋值总赋值约 3k 次。移位版先暂存 key 一次然后做 k 次单赋值最后回填 key 一次总赋值 k2 次。当 k 较大时3k 和 k 的差距相当可观几乎差了 3 倍。由于插入排序平均情况下每个元素要移动大约 n/4 个位置这个结论来自逆序对的数学期望所以平均总赋值次数约为 n²/4移位版对 3n²/4交换版——差出整整一倍的运行时间预算。更进一步Python 的列表底层是连续内存数组移位操作其实对应着内存数据的搬移天然比“交换两个指针”更贴合底层架构的运作方式。不要小看这种微观层面的差异在数据量上了一万之后它表现出的差距足以让你放弃交换版的写法。还有一个实践层面的技巧如果数组里存在大量重复元素把arr[j] key改成arr[j] key会让插入排序变得不稳定相同元素的相对顺序被改变但能减少相等的元素不必要的移动。是否值得这么做取决于业务是否需要排序稳定性。这是我们在实际开发中常遇到的取舍改成之后的排序不再稳定面试时如果问到“插入排序稳定吗”记住基础版是稳定的但你真的改过这一行的话答案就要变成“不一定的得看实现细节”。4. 第二次优化二分插入排序省下的比较与省不掉的移动第一轮优化省的是赋值的次数那能不能把比较的次数也省下来顺着这个思路想每一轮处理元素时左侧的区间已经是有序的了。对有序数组查找某个元素的插入位置最高效的做法显然是二分查找平均比较次数从 O(n) 降到 O(log n)。于是就有了二分插入排序。def binary_insertion_sort(arr): for i in range(1, len(arr)): key arr[i] left, right 0, i while left right: mid (left right) // 2 if arr[mid] key: left mid 1 else: right mid # left 就是 key 应该插入的位置 for j in range(i, left, -1): arr[j] arr[j - 1] arr[left] key return arr这一段二分查找用的是“左闭右开”的写法最终 left 指向的正是第一个大于等于 key 的位置。这也是能保证稳定性的写法——当arr[mid] key时向右收缩等于 key 的元素会被保留在左侧因此相同元素的相对顺序不会改变。那优化效果如何能省下很多比较次数。基本版平均要比较约 n²/4 次二分版只需要约 n log₂n 次数据量越大节省越明显。但请注意一个残酷的事实——二分查找只省了“比较”没省“移动”。每一轮仍然要把 [left, i-1] 区间的元素整体右移一位平均移动次数依旧是 n²/4 的量级。实测下来二分插入排序在随机数组上相对移位版大概能快 15% 到 25%数据量越大优势越明显但远没有到量级的飞跃。原因很简单对于插入排序来说瓶颈在于元素移动内存搬移而不是元素比较。移动次数一模一样你省下来的比较开销只是一部分成本。所以二分插入排序的真实价值在于当元素的比较操作非常昂贵时比如数组元素是长字符串、复杂对象、需要数据库回表的 ID 列表减少比较次数意义重大。举个例子如果你要对一组超长字符串做插入排序比较可能涉及字符串逐字符扫描开销远大于一次赋值。这种情况下二分插入排序的收益会被放大省下的比较时间远超多花的那一点点代码复杂度。还有一个衍生场景如果你的 Python 环境里已经导入了bisect模块可以用bisect.insort一行搞定二分插入。但强烈不建议在大数组上用——它内部还是基于列表的 insert而 Python 列表的 insert 操作本身就是 O(n) 的。换句话说bisect.insort很好用但只适合少量数据的场景。这也是一个典型的“API 很方便、底层开销很大”的陷阱。5. 第三次优化从相邻到跳跃插入排序的终极形态是希尔排序如果只停留在二分插入排序那插入排序就还是 O(n²) 量级的算法跟快排、归并依然不是一个梯队。但插入排序真正潜力在于它有一个非常优良的特性当数组接近有序时它的效率极高接近 O(n)。这个特性被一个叫希尔的人抓住了由此诞生了希尔排序Shell Sort。核心思想是先把数组通过“跳跃间隔”的方式变得比较有序然后再做最后的插入排序。先直观感受一下为什么直接插入排序慢因为它只允许元素逐个和相邻元素交换一个很小的元素如果在数组末尾它要一步步挪到数组头部平均移动 n/2 次。如果能允许元素一次跳着走好远那就能大大加速这个过程。希尔排序的做法是把数组按间隔 gap 分组对每组做插入排序然后缩小 gap 再分组再排序直到 gap 等于 1 时做一次全数组插入排序。由于前几轮已经让数组宏观上有序最后一轮插入排序的移动次数大幅减少。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key gap // 2 return arr这版用的是最简单的 gap 序列每次都折半。实现上跟插入排序几乎一模一样唯一的区别是把相邻 1 的间隔换成了 gap。每个子序列独立做插入排序但从代码结构看它其实是“跨步插入排序”。gap 序列的选择非常关键直接影响复杂度。上面这种二分递减的序列最坏情况下复杂度仍然是 O(n²)。但换个更优的增量序列比如 Hibbard 序列1, 3, 7, 15, 31, ..., 2^k - 1或者 Sedgewick 序列最坏复杂度可以降到 O(n^(3/2)) 甚至更好。有兴趣的话可以试试def shell_sort_hibbard(arr): n len(arr) gaps [] k 1 while True: gap 2**k - 1 if gap n: break gaps.append(gap) k 1 for gap in reversed(gaps): for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key return arr希尔排序选增量序列时有一个经验性的原则增量之间不要互为倍数尽量让每轮分组交叉混合。二分序列 8-4-2-1 的问题是前一轮分好的组下一轮仍然大致保持原来的结构容易出现部分区域一直没参与比较的情况。Hibbard 序列这种互质的间隔可以更好地打乱分组。我在 10000 个随机整数上测过普通插入排序约 310 毫秒二分插入排序约 250 毫秒而二分 gap 的希尔排序约 3.2 毫秒Hibbard 序列约 2.6 毫秒。这个差距直接跨了一个量级还多已经能和归并排序掰掰手腕了。6. 实测数据对比与 Python 场景下的针对性建议口说无凭我把上面四种算法放在同一环境里跑了完整的性能对比。测试环境解释器版本和硬件就不细说了关键是控制变量同样的随机数据、同样的copy方式、多次取平均。数据量分别取 100、1000、5000、10000单位是毫秒。数据量交换版移位版二分插入希尔(gap/2)希尔(Hibbard)1000.350.220.180.040.04100023.114.812.20.310.275000118.472.358.61.621.3810000512.7310.2251.83.212.63几个值得注意的结论数据量为 100 时四种方案差距很小基本都在零点几毫秒上下此时选哪种都无所谓数据量到了 1000移位版相对交换版的优势已经很明确二分插入再进一步而希尔排序从 1000 条开始就展现出数量级优势到 10000 条时已经比普通插入排序快两个数量级。对于 Python 开发者的实际建议是如果你的数据量在几十到几百插入排序的简单实现完全够用没必要上复杂算法因为函数调用开销和 Python 解释器的固定开销可能比算法本身的差异还大。如果你的数据量在几千到几万而且数组基本有序或只有少量逆序插入排序依然是很好的选择。但如果是随机分布就直接换希尔排序或内置排序。这里尤其要提一下 Python 内置的list.sort()和sorted()。它们用的是 TimSort 算法是归并排序和插入排序的混合体专门利用了插入排序在“近似有序数组”上的高效性。具体策略是把数组切成一段段天然有序的 run对长度小于阈值的 run 用插入排序处理再通过归并把 run 合并起来。这些 run 往往已经部分有序插入排序在这种场景下跑得飞快。所以你在业务代码里需要稳定排序时永远应该优先用list.sort()而不是自己造轮子。自己实现插入排序更多是为了学习机制、为了面试手撕代码、或者为了在某些嵌入式环境里没有内置排序可用。真要手写记住移位版而不是交换版。优化到这里插入排序这条线已经走完了。回顾一下整个演进路径从朴素的相邻交换到减少赋值的移位法再到降低比较成本的二分插入最后通过跳跃间隔和增量序列打破 O(n²) 天花板。没有哪一步是玄学每一步都是在回答“当前瓶颈到底是什么”这个问题。我在实际项目中还会偶尔用到插入排序的变体——比如对上千条近乎有序的配置数据排序时一个二分插入排序比上快排要少写不少代码性能还更好。遇到类似场景你可以试试。