如果你去翻任何一门语言的排序源码会发现插入排序和堆排序的内核都被塞进了标准库的某个角落。五大经典排序算法——插入、希尔、冒泡、选择、堆排序听起来像是教科书留给大学生的作业但我实际遇到的很多场景里它们仍然以各种形态出现一个近乎有序的数组没有被处理干净、一段需要保持稳定性的自研排序逻辑写错了方向、一个最坏情况退化到平方级的排序方案拖垮了整个接口。把这些算法彻底吃透不是应付考试而是给自己准备一套随时能用的底层工具。这篇文章会把每个算法的核心直觉、代码实现、复杂度推导、稳定性来源、边界细节一次性讲清楚中间穿插我实际练习和排查问题时积累下来的经验。无论你是准备面试的开发者还是工作中偶尔需要自己写排序的工程师读完应该都能直接上手并且知道在什么场景下该选谁。1. 先说清楚这五个排序算法今天到底还有没有用1.1 为什么语言自带排序还要自己会写绝大多数现代语言的标准库都提供了非常成熟的排序函数稳定、快、几乎无bug。那为什么还要自己动手写这五个经典排序第一个理由是面试和基本功。手撕排序几乎是最常见的算法考察方式尤其是插入排序、冒泡排序和快速排序的组合拳。第二个理由是可控性。内置排序是一个黑盒你不知道它内部什么时候退化成什么样也不知道它是否稳定、是否原地、是否允许自定义比较器。第三个理由是性能边界。内置排序在大规模随机数据上确实无人能敌但遇到近乎有序的数组、内存受限的嵌入式环境、对写操作代价极其敏感的存储场景时自己实现一个小而专的排序往往更合适。内置排序像打车自己会写排序像会开车。平时打车方便快捷但遇到特殊路线、车辆不可用、或者面试官让你解释发动机原理的时候会开就是硬实力。1.2 评价一个排序算法的三把尺子讨论排序之前先统一三把尺子时间复杂度、空间复杂度、稳定性。时间复杂度看三个值最好情况、平均情况、最坏情况。只背一个平均复杂度远远不够因为真实数据往往不是均匀随机分布。空间复杂度看是否是原地排序也就是除了输入数组本身是否还需要申请等量级的额外内存。稳定性指值相等的两个元素排序后它们的相对顺序是否保持不变。稳定性不是考试抠字眼它有非常实际的用途。举个最常见的例子一份订单列表先按下单时间排好序再按价格排序。如果第二次排序是不稳定的那么相同价格的订单之间原来的时间顺序就会被打乱最终结果既不是按价格正确排序也丢了时间顺序。多key排序、数据库索引、Excel的多次排序操作都依赖稳定性这个性质。1.3 五兄弟的家族划分与各自定位这五个算法其实可以分成两个家族。插入排序、冒泡排序、选择排序属于平方级O(n^2)家族它们实现简单、代码量小、教学价值高适合小规模数据和作为复杂算法的基础组件。希尔排序是插入排序的增强版通过大步分组让元素快速归位复杂度和增量序列强相关。堆排序属于O(n log n)家族它用完全二叉树的思想在数组中完成排序保证了最坏情况也不会退化。五兄弟各有各的定位插入排序是近乎有序数据的杀手锏希尔排序是中等规模数据的低成本方案冒泡排序是理解交换排序的活教材选择排序把交换次数压到最低堆排序则用最坏也能O(n log n)的稳定性兜底。后面的章节逐个拆开讲。2. 插入排序整理扑克牌式的直觉与近乎有序数据的杀手锏2.1 核心思路起牌、插位、腾挪插入排序的直觉藏在打扑克牌里。摸到一张新牌你会从右往左扫过手上已经排好的牌找到它该待的位置把比它大的牌依次往后挪一格然后把新牌插进去。对应到数组上就是从左往右维护一个前缀有序区。一开始前缀只有arr[0]天然有序。然后拿arr[1]往前看把它插进arr[0]前面或后面前缀变成两个有序元素。再拿arr[2]往前找把它插进正确位置前缀变成三个有序元素。以此类推直到整个数组有序。这个过程中每一轮处理的都是把一个新元素插进已经有序的前缀所以叫插入排序。它不需要额外数组完全在原来的数组上进行。2.2 实现代码与稳定性来源def insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key核心动作是两层循环。外层i从1到n-1逐个处理新牌内层把比key大的元素整体右移给key腾出位置。注意while条件里用的是arr[j] key严格大于而不是大于等于当两个元素相等时不触发移动新元素会落在旧元素后面相等元素的相对顺序被保持这就是插入排序稳定性的来源。如果改成arr[j] key虽然整体排序结果仍然正确但相等元素会被推到更靠前的位置稳定性就被破坏了。这个细节我在面试里问过很多人知道的人不多但一句就能证明你真的理解稳定性是怎么来的。2.3 复杂度推导为什么近乎有序时接近线性最坏情况是输入完全逆序比如[9, 8, 7, 6, 5, 4, 3, 2, 1]。处理第i个元素时它要一路挪到最前面移动i次。总移动次数是1 2 ... (n-1)也就是n(n-1)/2数量级O(n^2)。比较次数和移动次数同量级。最好情况是输入已经有序。每一轮内层while第一次比较就发现arr[j] key直接跳出。这时每轮只做一次比较、零次移动整体复杂度降到O(n)。平均情况下每个元素大约需要移动一半已排序区间的长度总代价仍然是O(n^2)。但注意O(n^2)的常数很小代码也几乎就是几行简单的赋值和比较。当n只有几十或几百时插入排序的实际速度完全不虚O(n log n)级别的算法因为后者有递归调用、函数栈、额外的逻辑分支。很多语言标准库内部的排序实现在处理元素数量小于某个阈值的小分片时都会切回插入排序就是这个原因。2.4 实战价值小规模与局部乱序的救星插入排序真正的用武之地是数据近乎有序的场景。比如一个系统每天生成几百条新日志时间字段大体有序只有零星几条乱序又比如一个有序数组里插入了几个新值需要重新排序。此时逆序对很少插入排序几乎以线性时间完成排序远比先全量快排再整体复制要高效。我实际测试过在一个10000个元素但只有0.1%乱序的数组上跑插入排序耗时和完全有序时几乎一样都是几个毫秒级别。而如果直接调用标准库排序虽然也能在一毫秒内完成但如果这个排序发生在频繁调用的热路径上能省的常数还是要省。这就是为什么很多语言标准库和数据库索引维护都在特定阶段使用插入排序。3. 希尔排序让插入排序先大步快跑再小步微调3.1 插入排序的瓶颈一格一格挪太慢插入排序一个明显的瓶颈是元素每次只能移动一格。如果最小的数出现在数组末尾比如[8, 7, 6, 5, 4, 3, 2, 1, 0]里的0它要经过n-1次移动才能到达开头。更难受的是后续每个元素都重复这个挪动过程整个数组被反复移动了很多次但每次移动的距离却很短。直觉上如果能让元素先跳着移动一大段距离快速接近它最终的位置再逐渐缩小步长精细微调那么总移动次数就会大幅度降下来。希尔排序做的就是这件事。3.2 分组大步排序希尔的核心思想希尔排序选定一个间隔gap把数组按间隔拆成若干逻辑分组。比如n10、gap4时下标0、4、8是一组1、5、9是一组2、6是一组3、7是一组。对每组分别做插入排序称为组内排序。完成后把gap缩小重新分组再做一轮组内排序。最后gap变成1时整个数组就是一个大组做一次标准插入排序收尾。注意最后一步必不可少。前面的大间隔排序只是让元素大致靠近目标位置不保证全局有序。gap等于1的最终插入排序是在近乎有序的基础上完成精确归位此时代价已经非常小。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): temp arr[i] j i while j gap and arr[j - gap] temp: arr[j] arr[j - gap] j - gap arr[j] temp gap // 2代码里有一点容易绕外层for从gap开始并不是先把第一组完整排完再排第二组而是每来一个元素i就把它往前跳gap个位置去插入。这等价于同时对所有分组做插入排序只是轮着来写法上比第一组全排完再排第二组更紧凑。3.3 增量序列决定希尔排序强弱的关键希尔排序对间隔序列的依赖非常大。最朴素的方案是每次除以2也就是gap从n//2一路减到1代码简单绝大多数场景够用。但如果想追求更好的性能数学研究者提出过很多增量序列比如Hibbard序列、Sedgewick序列它们能把最坏复杂度进一步压低。有意思的是增量序列到底怎么选才能达到理论最优至今没有一个公认的唯一答案只有一些实证效果很好的序列。工程上我建议直接用gap // 2就好。这个序列虽然最坏情况仍然是O(n^2)但平均行为已经很不错代码又简单不容易写错。为了那一点理论上限去折腾复杂序列得不偿失。3.4 稳定性与复杂度跳跃付出的代价希尔排序是不稳定的。因为分组跳跃两个值相等的元素如果被分到不同组组内排序时可能让它们交错或者远距离交换直接改变相对顺序。一个简单的例子[3, 5a, 5b, 4, 1]gap2时下标0、2、4是一组排完后5a和5b的顺序就可能乱掉。复杂度方面希尔排序没有像插入排序那样干净的平均复杂度闭合公式。使用gap//2序列最坏是O(n^2)使用更优序列最坏可以压到O(n^(3/2))甚至更低。实践中对中等规模数据希尔排序的速度往往比平方级算法高一到两个数量级又不像快排那样存在递归栈。它是那种用起来很省心的算法。4. 冒泡排序交换排序的活教材与标志位优化4.1 基础版本相邻比较最大值冒到底冒泡排序的思想最直白从头开始依次比较相邻的两个元素如果左边比右边大就交换它们。这样遍历完一轮最大的元素就像气泡一样冒到了数组末尾。下一轮处理前n-1个元素再把第二大的元素冒到倒数第二位。重复n-1轮整个数组有序。def bubble_sort(arr): n len(arr) for i in range(n - 1, 0, -1): for j in range(i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j]每一轮的内层循环范围都在缩小第一轮是0到n-1第二轮是0到n-2第i轮是0到n-i-1因为末尾i个位置已经被前面轮次冒上去的最大值占据了。4.2 标志位优化没有交换就提前收工朴素冒泡排序有个很大的浪费如果数组已经有序它仍然会傻乎乎地跑完全部n-1轮。优化方法很朴素每一轮开始前设一个swapped标志只要这一轮发生了交换就置为True。一轮结束时如果发现根本没有交换说明数组已经有序立即break退出。def bubble_sort_optimized(arr): n len(arr) for i in range(n - 1, 0, -1): swapped False for j in range(i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break这个标志位优化把最好情况从O(n^2)降到了O(n)。这是冒泡排序少数能拿得出手的优点之一已有序数据时一轮之后直接收工。但注意平均情况和最坏情况仍然是O(n^2)因为随机乱序数据很难提前结束。4.3 复杂度与缓存特征简单但有上限冒泡排序最坏和平均复杂度都是O(n^2)比较次数和交换次数都接近n(n-1)/2不只是量大交换本身比赋值更贵所以它通常比插入排序还要慢。我实测同规模随机数据冒泡往往比插入慢将近一倍原因就在交换太多。不过冒泡排序有两个正面价值。第一它是理解稳定排序和相邻交换的最佳教学工具代码只有几行逻辑一目了然。第二如果严格要求原地、稳定、代码极简且数据规模很小冒泡是一个不会出错的选项。有些变体比如鸡尾酒排序双向冒泡能稍微改善部分场景的性能但属于优化层面的小修补改变不了整体复杂度量级。5. 选择排序交换次数最少的朴素贪心策略5.1 思路与实现每轮挑最小放最前选择排序的思路像买菜挑最好的一颗从头到尾扫一遍找到最小的元素和第一个位置交换然后从第二个位置开始再扫一遍找到剩余元素中最小的和第二个位置交换。每一轮确定一个位置的最终值一共n-1轮。def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i]注意内层只记录最小值的下标而不是立刻交换扫描完一整轮之后才交换一次。这样每轮最多一次交换交换次数被压得极低。5.2 最少交换代价是固定不变的比较次数选择排序最大的特点是交换次数固定为n-1次这在五个算法里是最少的不考虑排序过程中额外的堆化操作。如果写操作代价极高——比如数据存储在写入成本敏感的介质上或者元素交换是一个昂贵的操作——选择排序的优势就显现出来了。但它的代价是比较次数固定为n(n-1)/2不会因为数据接近有序而减少。这一点和冒泡、插入很不一样那两个算法面对有序数据可以提前收尾选择排序不行。它每一轮都必须完整扫描剩余元素才能确定谁是最小值。所以最好、平均、最坏三种情况的时间复杂度全部是O(n^2)没有波动。5.3 不稳定性与正确性反例选择排序是不稳定的。看这个例子数组是[4a, 4b, 3, 2]其中4a和4b是值相同的两个元素。第一轮扫描全数组最小值是2下标为3。选择排序把2和arr[0]也就是4a交换得到[2, 4b, 3, 4a]。此时两个4的先后顺序从(4a, 4b)变成了(4b, 4a)相对顺序被破坏。为什么会出现这种情况因为选择排序做的是远距离交换它把最小值直接扔到当前未排序区的最前面这个最前面可能跨过很多与最小值同值的其他元素导致相同值元素被迫移位。如果后续还需要按其他key二次排序这种不稳定性会引发问题。6. 堆排序用完全二叉树在数组中完成原地排序6.1 最大堆与数组下标的关系堆排序的核心是把数组看成一颗完全二叉树并维护它满足堆序性任意父节点不小于它的两个子节点。满足这个性质称为最大堆堆顶就是全数组最大值。数组下标和树的位置有固定关系下标i的节点的左孩子是2i1右孩子是2i2父节点是(i-1)//2。借助这组关系树完全可以用数组原地表示不需要真正的树结构不需要额外内存。这是堆排序能实现原地O(n log n)的关键。有了最大堆排序思路很清晰把最大值堆顶放到数组末尾堆规模减一再维护剩下元素的最大堆性质再取堆顶放倒数第二位。循环下去数组就从小到大排好了。6.2 下沉堆排序唯一的原子操作堆排序的基本原语是下沉sift_down。对某个节点如果它的某个子节点比它大就把它和较大的子节点交换然后继续向下检查直到当前节点不比子节点小或者到达叶子。def sift_down(arr, n, i): while True: largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest i: break arr[i], arr[largest] arr[largest], arr[i] i largest下沉每次只下沉一层最多下沉log n层所以单次下沉的时间复杂度是O(log n)。这个函数写对堆排序就完成了一大半。6.3 自底向上建堆为什么是O(n)而不是O(n log n)建堆不是从根节点开始往下操作而是从最后一个非叶子节点开始倒着往前逐个下沉。最后一个非叶子节点的下标是n//2 - 1因为它的左孩子是2*(n//2-1)1正好落在数组末尾附近。从它开始倒着处理保证每次下沉时当前节点的左右子树已经是合法的堆下沉可以正确恢复堆序性。def build_heap(arr): n len(arr) for i in range(n // 2 - 1, -1, -1): sift_down(arr, n, i)这里有一个常被忽略的结论建堆的整体复杂度是O(n)不是O(n log n)。简单理解高度为h的节点大约有n/2^(h1)个每个节点最多下沉h层总操作数是约n乘以一个收敛的几何级数最后落在线性级别。这个结论来源直觉上反直觉因为看起来每个节点都要下沉log n层但实际上绝大多数节点都靠近叶子的位置下沉层数很小累加起来构成了线性复杂度。面试官很喜欢追问这一点能答上来是加分项。6.4 排序阶段反复取出堆顶建好最大堆之后排序阶段是一个简单的循环不断把堆顶元素和当前堆的最后一个元素交换让最大值固定到数组末尾再把堆规模减一对新的堆顶端点执行下沉。def heap_sort(arr): n len(arr) build_heap(arr) for end in range(n - 1, 0, -1): arr[0], arr[end] arr[end], arr[0] sift_down(arr, end, 0)排序阶段执行n-1次交换和n-1次下沉每次下沉O(log n)总复杂度O(n log n)。加上建堆的O(n)整体就是O(n log n)。因为这部分代价难以避免堆排序属于最坏也能保住O(n log n)的算法。6.5 复杂度与缓存不友好的现实堆排序的优势在理论上很漂亮原地排序、额外空间O(1)、最坏情况下也是O(n log n)、没有递归栈。但实际测试中同规模数据下它通常明显慢于语言标准库的排序实现。原因有两个。第一缓存不友好。堆排序的访问模式是跳跃式的下沉时从根节点跳到它的某个孩子再跳到下一层的孩子这些下标在数组中不是连续的CPU缓存命中率低。而插入排序、冒泡排序都是顺序扫描缓存非常友好。第二堆排序的常数大。下沉操作每一层都要做两次比较左孩子、右孩子排序阶段几乎都走满log n层就算数据已经有序也无法提前退出。堆排序适合的场景是要求原地、不允许递归、不能接受最坏退化的O(n^2)。除此之外大多数情况下语言内置的复杂混合排序往往结合快排、插入排序等多策略会跑得更快。7. 横向对决复杂度、稳定性与一次本机实测7.1 六维对比总表把五个算法的关键指标汇总成一张表方便随时查阅。算法最好平均最坏额外空间稳定核心特征插入排序O(n)O(n^2)O(n^2)O(1)稳定近有序、小规模王者希尔排序视增量序列通常观察接近O(n^1.3)视增量序列可达O(n^2)O(1)不稳定大步分组插入冒泡排序O(n)优化后O(n^2)O(n^2)O(1)稳定相邻交换教学首选选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定交换次数最少堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定原地、最坏不退化注意希尔排序的平均复杂度比较特殊它与增量序列强相关没有一个简单统一的公式。工程上用gap//2时中等规模数据表现很好但严格的理论上界仍然随序列变化。7.2 一次本机实测n10000随机整数我之前在某台机器上用同一份随机整数数组、同一个解释器分别跑了五个算法的纯Python实现时间大致如下算法n10000随机整数耗时插入排序约1.2秒冒泡排序约2.0秒选择排序约1.5秒希尔排序约0.02秒堆排序约0.03秒这份数据重点不在具体数值而在相对趋势。平方级算法在n10000这个规模已经是肉眼可见地卡顿而希尔和堆排序还在毫秒级。如果把n提高到100000平方级算法要跑到几十秒甚至几分钟希尔和堆排序仍然可以在一秒内完成。还有一个值得注意的现象同为平方级算法冒泡最慢插入其次选择稍快。原因是冒泡交换次数多插入排序虽然也移动元素但直接赋值比交换便宜选择虽然每轮比较很多但交换极少。这个差距在纯Python里会被放大在C语言里则会缩小但排序差异的方向基本一致。7.3 稳定性的工程意义多key排序时的选择依据前面反复强调稳定性这里集中说一下工程里怎么用。当你需要对一个数组按多个key依次排序时正确做法是倒着排先按最次要的key排再按更重要的key排最后按主key排。如果排序算法是稳定的前面每一轮的相对顺序都会被保留下来最终结果就是一个完美的多key排序。但如果用了不稳定排序比如选择排序或堆排序那么第二次排序会把第一次排序的结果彻底打乱。遇到这种需求稳定的插入排序或冒泡排序可以放心用不稳定算法则必须自己额外构造复合比较器把它合并成一次排序。8. 边界与经验手撕排序时最容易栽的坑和面试要点8.1 写之前先想清楚的三件事实际写任何排序代码之前先想清楚三件事输入规模多大是否需要稳定排序是否允许额外空间。规模小且要求稳定插入排序通常是首选规模中等且不要求稳定希尔排序够用规模大且最坏不能退化堆排序是底线方案需要做多key稳定排序则盯着插入排序和冒泡排序选。这三件事想清楚之后代码的大方向就不会错。然后立刻用几组最小用例自测空数组、单元素数组、[2, 1]、[1, 2]、[3, 3]。每次写完都跑一遍能躲掉一大半边界错误。8.2 五个算法最容易踩的边界错误下面这张表是我见过最常出的问题每一项都对应一个真实可见的错误现象。算法高频错误后果插入排序while里漏写j 0的等号访问越界或漏比较排序结果不稳定插入排序没有先保存key就移动数组元素被覆盖数据丢失希尔排序内层写成j 0而不是j gap跳过头分组逻辑错误冒泡排序内层range写成range(n - i)多比较一个已归位的位置可能访问越界选择排序min_idx没有初始化为i第一轮会和自己重复比较堆排序下沉时漏了left n或right n判断越界访问结果混乱堆排序建堆起点写成n // 2而不是n // 2 - 1多沉了一个叶子节点逻辑冗余但不报错堆排序的边界最容易出问题因为下标关系多。我练堆排序时第一次把排序阶段的sift_down(arr, end, 0)传成了n导致已经归位的末尾元素被再次卷入下沉逻辑排序结果从某个位置开始就不对了。这个错很隐蔽因为它不是崩溃而是静默出错——用最小用例验证才能发现。8.3 面试手撕排序的高频考点面试里手撕排序出现频率最高的是插入排序和冒泡排序因为代码短、逻辑清晰五分钟内就能写完。其次是堆排序重点考察建堆过程和下沉操作。很少让你直接写希尔或选择排序做第一问但会作为追问出现。常见的追问角度有四个这个排序稳定吗为什么最好情况是什么为什么堆排序建堆为什么是O(n)数据几乎有序时哪个排序最快答案是插入排序。回答的时候能顺手提一句插入排序在小n时比复杂排序更快所以很多内置排序会在小分片上回退到插入会显得你真的有工程经验。8.4 写在最后的一点个人体会我实际练习这些算法的最深体会是复杂度量级只是起点排序好不好用由常数、数据特征、稳定性和缓存行为共同决定。同一个O(n^2)插入排序在近有序数据上可以接近线性选择排序却永远慢吞吞同一个O(n log n)堆排序的常数和缓存表现又明显不如语言内置的混合排序。另一个体会是这五个经典排序是少有的能把理论复杂度和工程取舍串起来讲透的知识点。当年我为了把堆排序的下沉过程彻底搞明白对着数组一遍遍画二叉树下标关系花了整晚。后来真遇到一个内存受限、最坏不能退化、不允许递归的场景时我才意识到那晚的时间没有白费。如果你现在觉得这些算法离实际很远也先别绕开它们——它们会在某个排序需求突然出现的时刻变成你手边最可靠的底牌。