★ FEATURED ARTICLE 排序算法这事是每个程序员绕不过去的坎。不管你是刚准备校招的应届生还是工作了三五年想补基础的老手面试官总喜欢从排序算法切入然后再扔一个“稳定性和复杂度”的问题看你基本功扎不扎实。而我今天要写的这篇总结就是把八大排序算法摊开来一个一个拆给你看它为什么稳定为什么不稳定时间复杂度是怎么推出来的空间复杂度又在哪一步被消耗掉了。这篇内容适合所有需要系统梳理排序算法的人尤其是在面试冲刺阶段的同学认真看完你就不会再被“快排为什么不稳定”这种问题问住。排序算法说到底是数据结构与算法的基础题目但它的价值远不止应付面试。理解时间和空间复杂度能帮你在真实项目中判断数据规模下该选什么排序方案理解稳定性能让你在多字段排序、数据库索引维护、稳定分区等场景里少踩坑。下面这些内容我按“概念→逐算法拆解→汇总对照→工程选型→避坑自查”的顺序来写力求让你看完就能直接输出一套完整体系。1. 稳定性的底层逻辑为什么这个特性比想象中更重要1.1 什么是稳定性从一次排序丢序说起稳定性的准确定义很简单如果两个相等的元素在排序前后的相对位置保持不变那么这个排序算法就是稳定的反之就是不稳定的。举个例子有一组学生记录先按班级排好序再按成绩排序。如果第二次排序用的是稳定排序那么成绩相同的同学会继续保持班级顺序如果用的是不稳定排序成绩相同的同学班级顺序就乱了原始信息丢失。很多人第一次接触这个概念时觉得无所谓——反正值相等谁排在前面不都一样吗这种想法在纯数值场景确实没错但在实际业务里一条记录往往包含多个字段排序只是中间步骤。比如电商订单先按用户分组再按时间排序如果排序不稳定时间戳相同的订单就可能出现乱序影响分页展示的一致性。1.2 稳定性考察的真正用意面试官考察稳定性表面上是在问“你知道这个定义吗”实际上是在考察两件事第一你是否理解算法的交换逻辑会对相等元素的顺序产生什么影响第二你是否能在工程场景中意识到排序次序是有信息量的不能随手丢失。还有一个高频场景数据库的索引维护。很多数据库的排序操作天然要求稳定因为索引本身是多层级的底层数据位置一旦顺序错乱二级索引的维护成本就会飙升。再比如 MapReduce 或 Spark 中的二次排序也是利用稳定排序先按 key 排序再按 value 排序最后得到 key 有序且 value 有序的结果。如果你在这个环节里用错了排序算法数据整体错乱是最轻的问题严重时还会导致任务的正确性出问题。所以稳定性的价值不是理论上的挑剔而是工程正确性的底线。1.3 不稳定算法如何“补救”实操中有一种思路值得记录不稳定算法可以通过额外字段来“补救”。比如你给每条记录加一个自增序号排序时比较规则变成“先比较主键主键相同则比较序号”这样即使算法本身不稳定最终结果也具备稳定性。这个方案在数据量不大、内存允许的场景下非常实用我在处理复杂对象排序时经常用这招。代价是额外存储和比较开销但换来了逻辑上的稳定性价比很高。2. 八大排序算法逐一拆解时间、空间与稳定性的完整推导2.1 冒泡排序相邻交换决定了它天然稳定冒泡排序的核心操作是相邻元素两两比较如果左侧大于右侧就交换。这个过程每一轮都会把当前未排序区间的最大值“冒泡”到最右侧。它的稳定性来源于一个关键细节交换只发生在严格大于的情况下当两个元素相等时不做交换那么相等元素的相对顺序自然不会被破坏。时间复杂度方面冒泡排序有两层循环最外层执行 n 轮每轮内层最多比较 n-i-1 次所以总的比较次数大约是 n²/2时间复杂度就是 O(n²)。如果加了“本轮未发生交换则提前结束”的优化标记最好情况数组已经完全有序下只需要扫描一遍时间复杂度为 O(n)平均和最坏情况仍然是 O(n²)。空间复杂度为 O(1)因为它只需要一个临时变量做交换属于原地排序。这里有一个容易忽略的细节冒泡排序的交换次数等于数组的逆序对数量。逆序对多的时候交换开销很大所以实际工程中几乎不会有人用冒泡处理大数据量但它作为教学案例极好因为它能清晰展示“比较-交换”对稳定性的影响。2.2 选择排序看似简单却是不稳定的典型选择排序的思路是每轮从剩余元素中选出最小值然后与当前位置交换。第一轮扫描全部 n 个元素找到最小值第二轮扫描剩余 n-1 个元素中找到次小值依此类推。因为每一轮都要线性扫描未排序区域而总共要执行 n 轮所以无论输入数据是什么样的它的时间复杂度都稳定在 O(n²)既没有最好情况的优化空间也没有最坏情况的退化问题空间复杂度 O(1)。再说稳定性。选择排序不稳定不是因为它比较时动了手脚而是交换操作可能跨越多个中间元素。我举个例子输入[5a, 5b, 3] 第一轮找到最小元素 3与第一个位置的 5a 交换 结果[3, 5b, 5a]原本 5a 在 5b 前面交换后 5b 跑到了 5a 前面两个相等的 5 的相对顺序颠倒。这类情况在数组有小值“跨越”多个元素时特别明显。这个例子几乎每年都会出现在面试题里必须记住。那选择排序有没有稳定版本有思路是不要用“跳跃式交换”而是用“插入式平移”找到最小值后把它之前的所有元素都向后平移一位再把最小值放到目标位置。这样相等元素之间没有跨越操作就能保持稳定代价是移动次数变多常数项增大。不过在实际生产中这种稳定版很少使用因为你不如直接用插入排序。2.3 插入排序像理扑克牌一样稳定插入排序的思想极其贴合生活场景你打扑克牌时摸到一张新牌会从右往左找到合适位置插入让手里的牌始终保持有序。实现上从第二个元素开始把它依次与前面已经有序的部分比较找到合适位置插入相当于把比它大的元素都向右移动一位。插入排序是稳定的因为插入位置是“从右往左找第一个不大于当前元素的位置”也就是说相等元素不会越过彼此相对顺序保持不变。这一点和冒泡类似都依赖“严格大于才移动”的比较规则。时间复杂度上最坏情况是数组完全逆序每个元素都要移动到最前面比较和移动的次数都是 n²/2所以最坏 O(n²)。最好情况是数组已经有序每个元素只需要和前一个元素比较一次总共比较 n-1 次时间复杂度 O(n)。平均情况仍然是 O(n²)。空间复杂度 O(1)。插入排序虽然理论复杂度不低但在“基本有序”或“数据量很小”的场景下表现极好。工程上很多排序函数在数据量小于某个阈值时会从快排切换成插入排序比如 JDK 的 DualPivotQuicksort 在数据量小的时候就会用插入排序来处理原因就是插入排序在接近有序时几乎接近线性时间而且常数项非常低。2.4 希尔排序插入排序的增量升级稳定性的代价希尔排序是对插入排序的一种改进思路是先把相隔一定距离的元素组成一组对每组做插入排序然后逐步缩小这个距离直到距离为 1 时做最后一次完整插入排序。因为每一轮都让序列更加有序最后一轮插入排序的数据几乎接近有序所以整体效率远高于普通插入排序。希尔排序的时间复杂度取决于增量序列的选择。常见的希尔增量不断除以 2下时间复杂度约为 O(n²)如果使用更好的增量序列比如 Knuth 增量h h*3 1最坏复杂度可以降到 O(n^(3/2))。平均复杂度至今没有一个严格统一的数学结论不同论文给出不同范围一般工程上记为 O(n^1.3) 左右。希尔排序是不稳定的。原因在于分组后相等的元素可能被分到不同组各组独立插入排序时它们可能跨越相对位置。比如某个值 a 在元素 b 的前面但分到不同组后组间移动会让 b 跑到 a 前面。这种“跨组移动”天然破坏了稳定性。所以在需要稳定排序的场景里希尔排序是不被考虑的。空间复杂度方面希尔排序和插入排序一样是原地排序只需要一个临时变量所以空间复杂度 O(1)。2.5 归并排序分治思想的稳定代表用空间换时间归并排序的核心是分治法把数组不断对半拆分为小数组直到每个小数组只剩一个元素天然有序然后再把相邻的小数组两两归并成一个有序数组。整个过程像是对一棵二叉树的“后序处理”先处理左子树再处理右子树最后合并结果。时间复杂度非常稳定无论输入数据如何分布每轮都要对所有元素做一次归并扫描而递归的层级是 log₂n 层所以总复杂度固定为 O(n log n)不会出现快排那种最坏退化到 O(n²) 的问题。空间复杂度方面归并排序需要一个与原始数组等长的临时数组来承载归并结果所以空间复杂度是 O(n)递归调用栈的深度是 log n通常会与临时数组合并计算工程实现中以 O(n) 为主来进行描述。归并排序是稳定的。归并操作中的关键一行是当左右两半部分的元素相等时优先取左侧元素。这个“优先左侧”的处理保证了相等元素的相对顺序保持一致所以稳定性成立。归并排序有两个变体值得了解。第一原地归并排序试图用交换代替额外数组来降低空间复杂度但实现极其复杂常数因子很大实际很少使用。第二自底向上的归并排序迭代版本不需要递归栈只用循环控制子数组长度从 1 翻倍到 n逻辑更直观也更适合链表的排序场景。实际工程中链表排序几乎默认归并排序因为链表不支持随机访问而归并排序只需要顺序遍历。2.6 快速排序日常最快但稳定性是硬伤快排也是分治思想但和归并不同它是在“拆”的时候就做了大量工作。每次选一个基准元素把数组分成两部分小于等于基准的放左边大于等于基准的放右边然后递归处理左右两部分。这个拆分的核心操作叫分区partition实现方式有很多种最经典的是 Lomuto 分区和 Hoare 分区。时间复杂度上快排的平均复杂度是 O(n log n)因为每层分区一共要处理 n 个元素递归深度期望为 log n。但它有一个臭名昭著的最坏情况如果每次分区选到的基准都是当前部分的最小值或最大值分区极度不均匀递归深度变成 n此时时间复杂度就退化到 O(n²)。解决这个问题的方法有随机化基准、三数取中等能把最坏情况的概率降到忽略不计。空间复杂度主要来自于递归调用栈平均 O(log n)最坏 O(n)。快排不稳定的原因在于分区过程中的交换操作。比如经典的 Lomuto 分区中小于等于基准的元素会被交换到前面这种交换是“跨区间跳跃式”的可能让相等元素的相对顺序颠倒。举个例子输入[3a, 2, 3b, 1]基准取 3a 分区过程中3b 可能被交换到 3a 原来的位置附近 结果中 3b 可能出现在 3a 前面所以要回答“快排为什么不稳定”关键在于理解“分区时的交换不是相邻比较后的小步移动而是跨区间的跳跃式调整这种跳跃使得相等元素可能互相跨越”。尽管快排不稳定工程领域依然大量使用它就是因为它的常数项极小平均性能极为出色。很多标准库的排序函数底层就是快排的优化版本配合随机基准和插入排序兜底整体性能非常稳定。2.7 堆排序原地 O(1) 空间的 log n 算法但不稳定堆排序利用完全二叉树的结构来维护最大堆或最小堆。建堆过程是自底向上不断下沉调整让每个父节点都大于等于子节点。排序过程是反复把堆顶元素最大值与堆的末尾元素交换然后把堆的大小减一继续调整堆顶。建堆的时间复杂度是 O(n)这一步很多人会误算成 O(n log n)但实际上每个非叶子节点的调整代价与其高度相关整体求和是线性的。之后 n-1 次堆顶提取操作每次调整 O(log n)所以总时间复杂度是 O(n log n)。无论输入有序还是无序堆排序的执行时间都相对稳定这是它优于快排的地方。空间复杂度上堆排序是原地排序只需要常数级辅助空间所以是 O(1)。堆排序的稳定性问题比较隐蔽。看一个例子输入[5a, 5b, 1] 建堆后[5b, 5a, 1] 因为调整过程中 5b 被上浮到堆顶 然后把堆顶 5b 和末尾 1 交换得到 [1, 5a, 5b]原本 5a 在 5b 前面建堆时由于父节点与子节点比较时相等的元素也可以交换5b 就跑到 5a 前面了。更复杂的情况发生在排序过程中堆顶元素与末尾元素交换后末尾位置被固定下来而后续调整又可能改变其他相等元素的相对位置。中间的交换距离非常大跨越了多个位置稳定性根本无法保证。堆排序的实战意义主要在于对内存使用有严格限制、又需要 O(n log n) 性能的场景。比如一些嵌入式系统中的排序任务内存紧张且数据量较大堆排序就是合适的选择。2.8 计数排序非比较排序把稳定性玩明白了前面所有算法都属于比较排序它们的时间复杂度下界是 O(n log n)。那有没有可能突破这个下界答案就是非比较排序计数排序就是最典型的一种。计数排序的核心思路是先生成一个长度为“数据范围 k”的计数数组统计每个值出现的次数然后做前缀和处理得到每个值在输出数组中的最后一个位置最后反向遍历原始数组把每个元素放到计算好的位置上。一个干净的实现代码如下def counting_sort(arr): if not arr: return arr max_val max(arr) min_val min(arr) k max_val - min_val 1 count [0] * k for num in arr: count[num - min_val] 1 for i in range(1, k): count[i] count[i-1] output [0] * len(arr) # 反向遍历保证稳定性 for num in reversed(arr): idx num - min_val output[count[idx] - 1] num count[idx] - 1 return output这段代码里最有技术含量的一行是“for num in reversed(arr)”。为什么要反向遍历因为 count 数组里存的是“每个值最后出现的位置”反向遍历时每放一个元素位置信息就向前更新一个这样相同值的元素会按照原始顺序从后往前依次填入各自位置最终保持稳定。如果改成正向遍历相同值的相对顺序就会颠倒算法就变成不稳定了。计数排序的时间复杂度为 O(n k)空间复杂度为 O(k)这里 k 是数值范围。如果 k 远大于 n效率和空间占用都会变差。它最适合的是数据范围有限、且数据密集分布的整数排序场景比如按年龄排序、按成绩等级排序、按 IP 段统计等。基数排序是计数排序的扩展通过逐位排序实现更广范围的整数或字符串排序它内部每一位排序用的就是稳定排序通常是计数排序所以整体也是稳定的。桶排序则是把数据分布到有限个桶中每个桶内再用其他算法排序最终桶间是有序的稳定与否取决于桶内部算法是否稳定。3. 复杂度汇总与记忆体系一张表加一些口诀3.1 八大排序算法核心指标汇总以下是我整理的对照表把八种排序的时间复杂度、空间复杂度和稳定性集中到一起。建议你截图保存面试前过一遍排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(n^1.3)O(n)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(n k)O(k)稳定提醒一句希尔排序的时间复杂度与增量序列强相关不同教材给出的数据可能不同。面试时如果提到希尔排序主要说它“优于普通插入排序但具体复杂度依赖增量序列”即可不需要死记 O(n^1.3) 这个数字。3.2 记忆口诀和判断技巧背表格不是最佳方式更推荐用逻辑推演来记住结论稳定算法只有三个冒泡、插入、归并。再加上计数排序如果实现正确也是稳定。为什么这几个稳定因为它们都遵循“相等时不交换或归并时优先取左侧”的原则。不稳定算法有选择、希尔、快排、堆。为什么不稳定因为它们都涉及“跨越式移动”选择排序是跨越多个元素的最小值交换希尔排序是跨组移动快排是分区交换堆排序是跨度极大的堆调整。记忆口诀我这里提供一个思路“插冒归稳其余不稳”。四个字先记住稳定的集合剩下的自然是不稳定的。计数排序作为非比较排序单独记忆即可。时间复杂度的记忆也可以从原理出发。O(n²) 家族是冒泡、选择、插入都是两层循环暴力处理。O(n log n) 家族是归并、快排、堆排序都是利用了“分治”或“树”结构把层级降为 log n。希尔是插入排序的改进复杂度介于两者之间。4. 工程选型实战不同场景该用哪种排序4.1 数据规模决定一切我个人的经验法则是数据量小于 50 时直接插入排序实现简单且常数极小数据量在 50 到几千之间快排是默认选择数据量再大快排配合堆排序处理极端情况更稳妥如果数据范围很小比如年龄、分数、状态码这类有限枚举值计数排序是降维打击级别的好用。举一个实际场景某系统需要给一批订单记录按照金额排序。金额是浮点数范围不确定这时候计数排序就不适用了。订单量在几万级别金额可能存在大量重复这种情况下用快排虽然不稳定但业务上并不要求保持什么原始顺序所以没问题。但如果需求变成“先按优先级排序优先级相同时保持创建时间顺序”就需要一个稳定排序这时归并排序就是更合适的选择。4.2 内置排序函数的稳定性审查不同语言的内置排序稳定策略不一样这个必须知道Java 的 Arrays.sort() 对基础类型数组使用 DualPivotQuicksort它是不稳定的对对象数组使用 TimSort这是稳定的。Collections.sort() 同样基于 TimSort是稳定的。这是因为对象排序往往需要保留原始顺序信息而基础类型没有这个需求。Python 自带的 sort() 方法基于 TimSort它是稳定的。Go 语言在较新版本中排序实现为稳定排序内部不再混合不稳定快排。C 的 std::sort() 不保证稳定std::stable_sort() 保证稳定。如果你需要稳定性务必查阅语言标准库的排序说明不要假设所有内置排序都是稳的。这个点在实际开发中极易踩坑特别是在分布式系统中做二次排序时尤甚。4.3 混合排序策略的工程智慧真实工程的排序实现往往是“组合拳”。比如 TimSort 就是“归并 插入”的混合它先把数据切分成一个个短的有序片段片段之间用归并连接片段内部自然有序就跳过排序无序则用二分插入排序整理。这种混合策略让 TimSort 在数据部分有序时表现极佳时间复杂度能做到 O(n)而最坏情况仍然维持 O(n log n)。另一个例子是 JDK 的 DualPivotQuicksort它在数据量小的时候切换成插入排序在数据包含大量重复元素时采用三路快排的思路来优化。这种工程化的改进告诉我们理论算法是基础但落地时要针对数据的统计特征做适配。5. 高频面试题与易错自查清单帮你考试不翻车5.1 面试官最爱问的几个问题第一个问题为什么快排的平均复杂度是 O(n log n)回答思路是每一层分区操作要处理 n 个元素期望的递归深度是 log n因为基准值大概率会把数据分成相对均匀的两份所以总操作次数是 n 乘以 log n。但最坏情况下基准极端不均时递归深度变成 n时间复杂度就退化为 O(n²)。这个回答展示了你不只是背结论而是理解期望分析。第二个问题堆排序和归并排序都是 O(n log n)实际怎么选回答思路是堆排序空间 O(1) 且最坏性能有保证但常数因子较大实际运行速度通常慢于快排缓存局部性也差归并排序稳定且支持外部排序但需要 O(n) 额外空间。数据能全部加载到内存且空间充裕选归并内存受限且不需要稳定选堆排序。第三个问题有没有可能让所有排序都是稳定的回答思路是可以通过“稳定化改造”实现比如给每个元素增加唯一序号比较时先比原值、再比序号这样任何排序算法都能产生稳定结果。代价是额外的存储空间和比较开销。这也是面试官考察你“是否理解稳定性本质”的好题。第四个问题快排和归并的时间复杂度推导。回答思路是快排每一层分区的开销是 O(n)递归层数期望为 O(log n)归并每层归并开销也是 O(n)递归层数始终为 O(log n)。所以两者平均都是 O(n log n)。快排最坏退化的原因只在于基准选取导致递归层数加深。5.2 我见过最多的理解误区误区一认为快排最坏情况是“数组有序”。这确实是最常见的退化条件但要说明前提如果每次选基准都选到端点元素有序数组就退化了。用了三数取中或随机基准后有序数组反而是表现极好的情况因为它分区后一侧为空但不会退化成 n 层递归。实际上随机基准下退化成 O(n²) 的概率极低比中彩票还低。误区二把堆排序的空间复杂度记成 O(log n)。堆排序虽然后期交换堆顶元素时用了递归实现的下沉函数如果写成递归版会引入递归栈空间但工程实现通常用迭代栈空间为 O(1)。即使写成递归版递归深度也只是 log n 级别通常不作为主要空间复杂度来讨论。误区三认为插入排序是 O(n²) 所以一无是处。实际上插入排序在“基本有序”或“小规模数据”下是最快的排序之一。很多快排实现内部对小数组切到插入排序就是因此。误区四把选择排序和冒泡排序的稳定性搞混。两者虽然都属于 O(n²) 交换类排序但冒泡是相邻交换所以稳定选择是跨位置交换所以不稳定。记住核心区别在交换方式。5.3 一个综合自查清单学完排序算法后你可以用下面的问题来检验自己是否真正掌握了知识体系能否 30 秒内写出插入排序的正确代码并说明它为什么是稳定的能否讲清楚快排分区过程中哪一步会导致不稳定能否从归并排序的角度解释“外部排序”的基本原理能否推算出计数排序在数值范围 k 很大时为什么不适用能否回答“设计一个稳定的快排”这种扩展问题能否在 5 分钟内口述建堆过程并推导出建堆时间复杂度为 O(n)如果这些问题都能顺畅回答那你基本不需要再担心排序算法这个考点了。我在实际工程和面试辅导过程中最大的体会是排序算法的价值不在于死记硬背结论而在于建立一套“从数据特征出发选择算法”的思维框架。核心指标的对比表值得收藏但更值得做的是亲手把每个排序实现一遍。尤其在你写出计数排序的反向遍历代码调试到答案正确的那一刻稳定性这个概念就不再是抽象的定义而变成你手下的代码逻辑了。这层内化的功夫才是扎实的基础。
阅读完成 · 觉得有帮助？
