排序算法这东西科班出身的人大学里多少都学过工作几年的老码农也不见得能徒手把每种细节都写对。前阵子我帮团队做一次代码评审发现一个功能里明明只需要取前K个最大元素结果有人直接写了个冒泡排序去排整个数组数据量一上来立刻被打回原形。很多人把排序算法当成“面试八股”背完就忘真正到了工程现场遇到几万条数据、内存敏感、稳定性有要求这些现实约束反而不知道怎么选。这五种算法——插入、希尔、冒泡、选择、堆排序之所以被反复拿出来讲是因为它们本质上覆盖了排序问题的几条经典解决路径逐步插入、分组跳跃、相邻交换、极值选择、堆结构利用。把这五个吃透往后看快排、归并、基数排序你会觉得框架特别清晰。这篇就把它们掰开揉碎讲一遍从原理到代码再到坑点尽量做到看完能直接“抄作业”。1. 先把五种排序放在一起掂量掂量——凭什么它们能被称为经典很多初学者学排序有一个误区就是上来先背代码背完五六个实现觉得“排序我会了”。但真到了用的时候面对一个具体的业务场景根本不知道选哪个。所以我想先花一点篇幅把这五种排序的本质差异讲清楚建立坐标系后面每个算法的细节才不会散。1.1 用生活场景理解五种排序的“人设”先说插入排序。你打扑克牌抓牌的时候每抓一张新牌会从右往左跟已有的牌比较找到合适的位置插进去。这个行为就是插入排序。它特别擅长处理“整体已经基本有序”的数据比如一个有序列表里新增几条记录这时候插排的效率接近线性。希尔排序是插入排序的改良版核心思路是“先粗调后精调”。它允许元素每次跳跃一大步让序列快速接近有序最后再用普通的插入排序做收尾。生活类比的话有点像整理书架先把书按大类粗略归位再在每一类里细致排好这比一本一本挨着挪效率高。冒泡排序最直观。每轮从头到尾两两比较把大的往后“浮”到末尾就像气泡往上冒。它的优点是代码极其简单、逻辑几乎不可能写错缺点是慢数据稍微多点就显得笨重。选择排序的思路是“贪心式挑选”。每一轮从未排序区域找到最小值放到已排序区域的末尾。它的特点是交换次数很少最多只有n-1次交换但比较次数一点都没省永远都是O(n²)。堆排序则换了一条路先把数组整理成一个二叉堆让最大值自动浮到堆顶然后反复把堆顶和末尾交换并缩小堆的范围继续调整。它把排序问题转化成了堆结构的维护问题能做到O(n log n)的时间复杂度而且空间开销极小原地就能完成。这五种思路你仔细品一下其实代表了五类完全不同的问题解决方法增量构建、分组渐进、局部交换、全局选择、结构改造。后面学快排分治和归并分治合并的时候你会发现自己对这些思路的敏感度明显提升了。1.2 复杂度与稳定性速查表算法对比的时候最怕只背一个“平均复杂度”因为工程场景里数组往往不是随机分布的——可能是接近有序的、含大量重复值的、或者逆序的。所以我把最好、最坏、平均、空间、稳定性全部列出来这是判断算法在特定数据形态下表现的基础。算法最好时间最坏时间平均时间空间稳定性插入排序O(n)O(n²)O(n²)O(1)稳定希尔排序O(n log² n)O(n²)O(n^1.3~1.5)O(1)不稳定冒泡排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定这张表有两个地方值得注意。第一个是“稳定性”。稳定指如果两个值相等排序后它们的相对顺序不会改变。这一点在业务里非常重要比如多条订单有相同的创建时间你希望保持它们原来的先后顺序那就必须用稳定排序。我见过不少团队因为没注意这个特性用不稳定排序导致列表顺序跳动用户都反馈过好几次。第二个是希尔排序的复杂度很有意思它不像另外四种有教科书级别的定论因为它的时间复杂度严重依赖于步长序列的选择。这也是它工程上比较尴尬的地方没有一个公认最优的gap序列实际操作里常常靠经验拍一个。后面我会具体展开。2. 插入排序与希尔排序从逐个插入到分组跳跃这两个算法先放在一起讲因为希尔排序是插入排序的直接进化版理解了插入排序再去看希尔排序会像看一条成长曲线。2.1 插入排序像整理扑克牌一样搞定局部有序插入排序的思维起点特别朴素假设数组左边已经是有序的我们拿右边第一个元素向左找到合适的位置把它插进去。整个过程反复执行有序区逐步扩大直到整个数组有序。写成代码就是这样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 return arr这段代码的核心是那个while循环。每次我们先把当前元素存到key里然后不断把比key大的元素往后挪让出位置。一旦遇到一个不比key大的元素循环终止把key放在它后面。很多新手会纠结一个问题为什么最后要arr[j1] key而不是arr[j] key因为while退出时j已经停在了“第一个不比key大的元素位置”的前一位所以key真正要放的位置是j1。插入排序最舒服的场景是“数组接近有序”。比如一个有序数组你往里面额外追加了几条记录大部分元素已经各就各位那while循环往往循环一两次就停了整体复杂度会非常接近O(n)。我在实际项目里做日志表按时间排序时因为时间戳本身天然接近有序直接用的就是插入排序效果比快排还好。2.2 插入排序的实现与边界处理我自己在写插入排序时最容易翻车的边界条件有两个。第一个是i从几开始。如果i从0开始key arr[0]然后j -1整个while不会执行没意义。所以i必须从1开始因为左边第一个元素天然是一个有序区。第二个是while循环里arr[j] key这个判断决定了排序的稳定性。如果写成那么遇到相等的元素时当前元素会跑到相等元素的前面去破坏稳定性。使用严格大于相等的元素保持原顺序插排才是稳定排序。还有一个性能上的小优化虽然O(n²)跑不掉但能减少一些无谓的赋值。很多教科书版本在内部循环里每比较一次就交换一次等于每次挪动都要写三次临时值。更高效的做法是我上面那种先把key拎出来内层只做arr[j1] arr[j]的单向覆盖最后再放key。赋值次数从3n次降到n次左右数据量大的时候体感差别还是明显的。2.3 希尔排序用间隔打破插入排序的“搬运困局”插入排序最大的缺点是什么是元素只能一步一步地挪。如果一个很小的元素在数组最右边它要穿越整个数组才能到最左边中间每一步都伴随着大量比较和移动。数据量大、顺序混乱时这个搬运成本极高。希尔排序的思路就是先“大步走”再“小步走”。它先选一个较大的间隔gap把数组按间隔分成若干组每组内部做插入排序。等每组排完再缩小gap重新分组排序直到gap变成1。最后一次gap1时整个数组已经离完全有序不远了此时插入排序的优势正好发挥出来。每次分组插入排序都让无序的数据快速跳跃到大致正确的位置附近后续过程只需要做微调。这就是它比纯插入排序快得多的核心原因。2.4 希尔排序的gap选择与实现希尔排序的核心问题是怎么选gap。常见的策略有几种Shell原始序列n/2, n/4, ..., 1。简单粗暴但效率一般。Hibbard序列1, 3, 7, 15, ..., 2^k-1。最坏能到O(n^1.5)。Sedgewick序列1, 5, 19, 41, 109...这种组合序列实测效果更稳定。工程上最省事的就是用n不断除以2来生成gap因为实现简洁不用预生成序列。以下是一个典型实现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 return arr注意这里和普通插入排序的区别在于普通插排里j每次减1这里j每次减gap普通插排的边界是j 0这里是j gap因为要保证arr[j-gap]索引有效。写希尔排序的时候有一个特别容易误解的点对每个gap并不是先排完一组再去排下一组而是从左到右扫描一次每组交替地插入排序。这种“轮流处理各组”的方式叫“交错插入”代码写起来简单效果和一组一组分别排是一样的。希尔排序的稳定性问题也要特别警惕。由于分组跳跃相等的元素可能被分到不同组或者在某轮中被交换跨越到其他相等元素前面所以它是不稳定的。我在项目里凡是依赖稳定性的场景都不会选希尔排序。3. 冒泡排序与选择排序简单但不平庸的老实人方案这两种排序经常被初学者当成“入门必备”因为代码最短、逻辑最直白。但正因为看起来简单很多人会忽略它们在不同数据条件下的行为差异。这里我想把它们的原理和优化讲透。3.1 冒泡排序的原理与基础实现冒泡排序的核心是两两比较如果顺序错误就交换。每一轮结束后当前未排序区最大的元素会被“顶”到未排序区的最后面就像气泡一样上浮。最基础的实现def bubble_sort(arr): n len(arr) for i in range(n): for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return arr这里内层循环的终点是n - 1 - i因为每一轮结束数组末尾i个位置已经是有序区没必要再参与比较。很多人写内层循环时忘记-i结果每次都从头比到尾虽然功能正确但白白多做了很多工作。3.2 冒泡排序的两个常用优化第一个优化是“提前终止”。如果某一轮从头到尾都没有发生交换说明数组已经完全有序此时可以提前break。这个优化在数组基本有序时效果极佳能让复杂度从O(n²)直接降到O(n)。def bubble_sort_opt(arr): n len(arr) for i in range(n): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr第二个优化是“记录最后交换位置”。每一轮里最后一次交换发生的位置之后的所有元素都已经有序下一轮内层循环只需要扫到那个位置即可。比如数组是[1,2,3,4,5,7,6]第一轮交换完最后一次交换位置在索引4那么索引5之后的元素已经有序下一轮就没必要再比较到n-2只需要比到4。这个优化适合“前半段乱、后半段已经有序”的数据形态在工程里很实用。我处理过一批按时间戳倒序的日志大部分数据尾部已经有序用这个优化后耗时下降了近一半。3.3 选择排序的原理与实现选择排序比冒泡还要“懒”。它每一轮只做一件事在未排序区域找最小值的下标然后把最小值跟未排序区的第一个元素交换。一轮一个n轮后全部排完。def selection_sort(arr): n len(arr) for i in range(n): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] return arr选择排序的好处是交换次数非常少最多只有n-1次交换而冒泡排序在最坏情况下的交换次数高达n(n-1)/2。当交换的成本高于比较的成本时选择排序反而比冒泡快。现实里这个场景确实存在比如数组元素是巨大的对象每次交换需要读写大量数据而比较只是比较几个简单字段此时选择排序的优势会被放大。3.4 选择排序的稳定性问题到底怎么回事选择排序之所以不稳定核心在于“远距离交换”。假设数组是[5, 3, 5, 2]两个5值相等。第一轮找到最小值2和第一个5交换数组变成[2, 3, 5, 5]。注意原来的第一个5跑到了数组末尾原来的第二个5留在了原第一个5的位置两个相等元素的相对顺序被改变了。这个细节在业务上会引发一个非常隐蔽的bug如果你先按时间排序再按名称排序名称相同的数据因为不稳定算法被乱序最终列表看起来会“随机跳动”。尤其做排行榜、订单列表这类对顺序有明确要求的页面时这个问题会被用户直接感知。所以在工程里如果同时需要“排序”和“保持原有顺序”优先考虑稳定算法。4. 堆排序线性建堆与堆顶置换的精髓堆排序是这五种里代码量最大、思维难度最高的一个但也是第一次让你体会到“数据结构”在排序里的威力。不少面试者能背出快排一到手写堆排序就卡壳问题多半出在堆调整这一段。下面我详细拆解。4.1 堆结构到底怎么组织堆在概念上是一棵完全二叉树但在实现上完全可以借助数组下标来模拟。假设一个数组长度为n下标从0开始那么下标i的父节点是(i - 1) // 2下标i的左孩子是2 * i 1下标i的右孩子是2 * i 2最大堆的性质是“堆顶元素最大每个父节点都大于等于它的孩子节点”。这个性质不需要每层都严格有序只需要满足局部父大于子的关系即可。堆排序的思路分三步把数组调整成最大堆。把堆顶即最大值和数组末尾交换此时最大值到了最终位置。把堆的范围缩小一格对新堆顶做下沉调整恢复堆性质。重复直到堆的范围只剩一个元素。要让堆排序的效率有保障关键在建堆和调整两个操作上都保持O(log n)级别的成本。4.2 堆排序实现完整流程我自己习惯用一个heapify函数来处理下沉逻辑。它的参数是数组、堆大小、当前要下沉的节点下标。def heapify(arr, heap_size, root): largest root left 2 * root 1 right 2 * root 2 if left heap_size and arr[left] arr[largest]: largest left if right heap_size and arr[right] arr[largest]: largest right if largest ! root: arr[root], arr[largest] arr[largest], arr[root] heapify(arr, heap_size, largest)然后堆排序主体def heap_sort(arr): n len(arr) # 建堆从最后一个非叶子节点开始向上调整 for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 逐个取出堆顶 for i in range(n - 1, 0, -1): arr[i], arr[0] arr[0], arr[i] heapify(arr, i, 0) return arr有几个点需要特别说明。最后一个非叶子节点的下标是n // 2 - 1。为什么因为最后一个元素的下标是n - 1它的父节点是((n - 1) - 1) // 2 n // 2 - 1。从它开始往前逐个heapify能保证每次调用时它所管辖的子树已经满足堆性质上浮式的调整效率最高。交换堆顶和末尾后堆的范围从n变成了i此时只有堆顶不满足堆性质而它左右子树仍然是合法的堆。调用heapify只需要下沉一个节点代价是O(log n)。所以整个堆排序的复杂度是建堆O(n)加上n次下沉O(n log n)总复杂度O(n log n)。4.3 堆排序的复杂度分析与使用心得很多人对建堆复杂度是O(n)感到意外直觉上n/2个节点每个都要下沉怎么会是O(n)原因在于高度越高的节点数量越少各层代价加起来是一个收敛的等比级数总复杂度仍是O(n)。这个推导属于经典结论面试时能说出来会很加分。堆排序最大的优点是原地排序、不需要额外空间空间复杂度只有O(1)。因此在内存极紧张的嵌入式场景里堆排序是很可靠的选择。但它有一个短板它访问内存的方式跳跃性很大不像插入排序那样顺序访问缓存命中率不高。在数据规模较大、内存调度频繁的情况下虽然理论复杂度是O(n log n)实际运行却可能比快速排序慢不少。这也是工程里大量默认排序库选快排而不是堆排的原因。另外提醒一句堆排序也是不稳定排序。因为堆顶交换这个动作会让相同元素的相对顺序发生改变。用到堆排序前先问自己一句稳定性能不能接受不能的话老老实实选归并或者插排。5. 五种排序怎么选工程实践中的取舍标准到这里五种算法都讲完了但更深一层的问题是“我到底该用哪个”。这个问题的答案不能只看复杂度表还要结合数据形态、内存限制、稳定性需求、代码可维护性来综合判断。5.1 不同数据规模下的表现差异我梳理一个实际排序场景的选择清单仅供你参考数据量很小比如几十个元素插入排序最省心代码简单常数因子小实测和快排不相上下。数据量中等几千到几万个元素且接近有序插入排序或者希尔排序都很合适。数据量较大比如十万以上且顺序随机堆排序和快排是常客。如果不想引入递归深度的风险堆排序更保险。数据量极大但只关心前K个堆排序简直量身定做只需要维护K个元素的小顶堆复杂度是O(n log K)比全排一遍快一个量级。数据基本有序冒泡排序加上提前终止优化后有一个很惊喜的表现因为第一轮扫描可能就发现不需要交换整体复杂度接近O(n)。数据重复度较高选择排序因为有大量无差别比较表现中规中矩插入排序和希尔排序则表现较好因为重复元素能快速跳过。我实际做过的压测里一个长度为20000的接近有序数组纯插入排序比快速排序还快。原因就是插排的顺序访问特征在CPU缓存上占了大便宜。这一点在工程上很有参考价值别迷信“快排一定最快”这句话。5.2 稳定性是否需要一个容易被忽视的决策因素很多刚工作的开发者在写排序时完全不会考虑稳定性。但稳定性在业务里的地位远比想象中高。举一个真实场景一个商品列表需要按销量降序排列销量相同时保持后台设置的推荐顺序。如果你的排序算法不稳定同一批商品在排序前后的位置就会发生变化用户可能觉得页面在“抖”。正确的做法是使用稳定排序比如插入排序或归并排序或者先用稳定排序对推荐顺序排序再对销量做二次排序。如果因为算法性能原因一定得用不稳定排序那么可以通过“给每条数据附加一个自增序号把序号作为次要排序键”来抵消不稳定性。这也是我常用的手段代价是额外带宽和内存但能保住正确性。5.3 工程中的极端情况补充接近有序、大量重复元素这里展开几种容易踩坑的数据形态。第一种是完全逆序的数组。插入排序在这种输入下会退化到O(n²)因为每个新元素都要挪到最前面。冒泡排序同样糟糕。但希尔排序因为有多轮大步跳跃性能相对好很多。所以如果无法提前知道数据分布优先选希尔排序或堆排序更稳。第二种是含大量重复元素的数组。冒泡排序和插入排序的推进速度其实不差因为重复元素不会触发交换但选择排序无论数据长什么样都要比较到底。堆排序在重复数据下也能保持稳定有效的下沉表现因此大规模重复数据场景里堆排序是更稳的选择。第三种是“几乎有序但有个别元素错位”。这种情况插入排序几乎是最完美的因为错位元素经过几次移动后整个数组就完全有序了。原来O(n²)的复杂度在这种数据形态下会无限接近O(n)。6. 常见问题与排查技巧实录这一节我把在实际写这些排序时最容易出现的问题集中列出来有些是我带新人时反复纠正过的有些是我自己早年踩过的坑希望你不要再浪费时间去查。6.1 边界条件为什么数组中每次都要-1索引越界和漏比是排序代码里最常见的老鼠屎。以冒泡排序为例内层循环for j in range(n - 1 - i)很多人会写成n - i此时最后一次比较的索引是n - i再取arr[j1]就会越界。同理插入排序的while j 0条件如果写成j 0第一个元素就永远不会被比较排序结果错误。选择排序里外层i循环到n-1即可因为最后一个元素不需要再找最小值跟谁交换。我调试这些边界问题的方法很原始但有效找一段短数组比如[5,1,4,2,3]用纸笔或单步打印每次循环后的数组内容对比预期。人肉模拟两三轮之后边界条件基本一眼就能看出来。6.2 稳定性误解选择排序和希尔排序的坑我见过有人面试时拍胸脯说选择排序是稳定的理由是“它没像冒泡那样频繁交换”。这个说法是错的。判断稳定性只看一点相等元素的相对顺序是否能保持。选择排序的问题出在“从远处拿最小值过来交换”。哪怕你写代码时用了arr[j] arr[min_idx]而不是也无法保持稳定性因为那个最小值往往跨了很多个元素飞到前面来中间相等的元素被它挤到了一侧。这个bug在排序对象是结构体时尤其隐蔽因为你看不到相等元素的相对顺序变化。希尔排序同理分组跳跃让相等元素可能在某一组里越过另一个相等元素。所以凡是涉及“按多个字段二次排序”的场景都不要用这两种。6.3 堆排序索引错位问题节点、左右孩子与父节点堆排序的索引关系是node i - left2i1, right2i2这个公式看似简单但有三个容易出错的地方。一是当数组下标从0开始时父节点公式必须用(i-1)//2如果直接i//2来计算某个节点的父节点下标会在i1时出错因为1//20没问题但2//21会让节点2的父节点指到自身。二是heapify里必须在更新largest之后再去递归调整交换后的子树。很多人写完交换就结束导致子树内部的堆性质没有被恢复排序结果错误。三是建堆循环的起点n//2-1必须包含如果从n-1开始所有叶子节点都会被调用一次heapify虽然不会出错但白白增加开销。叶子节点本来就没有孩子heapify内部两个if都不会成立纯属浪费。6.4 性能实测与调试方法我调试排序算法性能的时候习惯先构造几种典型输入来跑基准随机数组测试平均性能。已排序数组测试最好性能和提前终止优化的效果。逆序数组测试最坏性能。重复元素数组测试稳定性带来的影响。跑的时候把数据规模从1千、1万、10万逐级增大记录耗时。你会发现很有意思的规律小规模时插入排序反而可能击败堆排序因为常数因子小但到十万级后O(n log n)算法的优势就非常明显了。如果发现自己写的排序在大数据量下耗时异常优先检查是不是存在多余的交换。比如冒泡排序里每轮多交换了一次或者选择排序里每次找到最小值就马上交换而不是走完一轮再交换。这些细节会显著影响常数因子。个人体会与一点建议我自己的感受是排序算法写起来难不难其实不取决于代码能不能跑通而取决于你有没有把“为什么这么写”想明白。比如插入排序为什么能把比较和移动分开希尔排序为什么需要多轮缩小的gap堆排序为什么能原地完成。这些问题想通以后代码只是顺带的产物。最后分享一个小技巧你可以把这五个算法写成一个统一的排序工具模块函数的第一个参数接收一个compare回调函数这样任何类型的数据都能复用。回调里如果返回负数代表a小于b正数代表a大于b。这样一来你在业务里既不用担心int数组排序的问题也不需要为每类数据单独写一套排序逻辑。排序看起来是个老掉牙的话题但我在实际项目中依然经常被它卡住。希望你读完这篇攻略后不只是会背代码而是能真正理解每个算法背后的取舍与代价在工程里做出正确的选择。