如果你去翻任何一门语言的排序源码，会发现插入排序和堆排序的内核都被塞进了标准库的某个角落。五大经典排序算法——插入、希尔、冒泡、选择、堆排序，听起来像是教科书留给大学生的作业，但我实际遇到的很多场景里，它们仍然以各种形态出现：一个近乎有序的数组没有被处理干净、一段需要保持稳定性的自研排序逻辑写错了方向、一个最坏情况退化到平方级的排序方案拖垮了整个接口。把这些算法彻底吃透，不是应付考试，而是给自己准备一套随时能用的底层工具。这篇文章会把每个算法的核心直觉、代码实现、复杂度推导、稳定性来源、边界细节一次性讲清楚，中间穿插我实际练习和排查问题时积累下来的经验。无论你是准备面试的开发者，还是工作中偶尔需要自己写排序的工程师，读完应该都能直接上手，并且知道在什么场景下该选谁。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，把数组按间隔拆成若干"逻辑分组"。比如n=10、gap=4时，下标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]，gap=2时，下标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的节点的左孩子是2i+1，右孩子是2i+2，父节点是(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^(h+1)个，每个节点最多下沉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 一次本机实测：n=10000随机整数我之前在某台机器上，用同一份随机整数数组、同一个解释器，分别跑了五个算法的纯Python实现，时间大致如下：算法n=10000随机整数耗时插入排序约1.2秒冒泡排序约2.0秒选择排序约1.5秒希尔排序约0.02秒堆排序约0.03秒这份数据重点不在具体数值，而在相对趋势。平方级算法在n=10000这个规模已经是"肉眼可见地卡顿"，而希尔和堆排序还在毫秒级。如果把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)，堆排序的常数和缓存表现又明显不如语言内置的混合排序。另一个体会是：这五个经典排序是少有的能把"理论复杂度"和"工程取舍"串起来讲透的知识点。当年我为了把堆排序的下沉过程彻底搞明白，对着数组一遍遍画二叉树下标关系，花了整晚。后来真遇到一个内存受限、最坏不能退化、不允许递归的场景时，我才意识到那晚的时间没有白费。如果你现在觉得这些算法离实际很远，也先别绕开它们——它们会在某个排序需求突然出现的时刻，变成你手边最可靠的底牌。
如果你去翻任何一门语言的排序源码，会发现插入排序和堆排序的内核都被塞进了标准库的某个角落。五大经典排序算法——插入、希尔、冒泡、选择、堆排序，听起来像是教科书留给大学生的作业，但我实际遇到的很多场景里，它们仍然以各种形态出现：一个近乎有序的数组没有被处理干净、一段需要保持稳定性的自研排序逻辑写错了方向、一个最坏情况退化到平方级的排序方案拖垮了整个接口。把这些算法彻底吃透，不是应付考试，而是给自己准备一套随时能用的底层工具。这篇文章会把每个算法的核心直觉、代码实现、复杂度推导、稳定性来源、边界细节一次性讲清楚，中间穿插我实际练习和排查问题时积累下来的经验。无论你是准备面试的开发者，还是工作中偶尔需要自己写排序的工程师，读完应该都能直接上手，并且知道在什么场景下该选谁。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，把数组按间隔拆成若干"逻辑分组"。比如n=10、gap=4时，下标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]，gap=2时，下标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的节点的左孩子是2i+1，右孩子是2i+2，父节点是(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^(h+1)个，每个节点最多下沉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 一次本机实测：n=10000随机整数我之前在某台机器上，用同一份随机整数数组、同一个解释器，分别跑了五个算法的纯Python实现，时间大致如下：算法n=10000随机整数耗时插入排序约1.2秒冒泡排序约2.0秒选择排序约1.5秒希尔排序约0.02秒堆排序约0.03秒这份数据重点不在具体数值，而在相对趋势。平方级算法在n=10000这个规模已经是"肉眼可见地卡顿"，而希尔和堆排序还在毫秒级。如果把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)，堆排序的常数和缓存表现又明显不如语言内置的混合排序。另一个体会是：这五个经典排序是少有的能把"理论复杂度"和"工程取舍"串起来讲透的知识点。当年我为了把堆排序的下沉过程彻底搞明白，对着数组一遍遍画二叉树下标关系，花了整晚。后来真遇到一个内存受限、最坏不能退化、不允许递归的场景时，我才意识到那晚的时间没有白费。如果你现在觉得这些算法离实际很远，也先别绕开它们——它们会在某个排序需求突然出现的时刻，变成你手边最可靠的底牌。