排序算法这四个字，可能是很多人入门编程时最早接触、也最容易敷衍过去的一类知识点。我见过不少开发者，面试前临时背一背快速排序，写业务代码时永远调用语言内置的sort()，可真要让他们解释一下“稳定排序和不稳定排序有什么区别”，或者在内存受限的环境里手写一个可用的排序方案，反而会卡壳。排序算法当然不只是为了把数据排整齐，它其实是理解算法复杂度、递归思想、数据交换策略最自然的切入材料。这篇文章想和你聊的，就是如何用最简单的方式把常见排序算法看透，既能写得出，也知道自己到底在用哪种套路、为什么这么选。
这篇内容适合刚准备算法面试的新人，也适合写过好几年业务代码、却一直没有系统整理过排序知识的开发者。我会从思路、代码、复杂度、实际坑点几个角度展开，尽量把一些书本上不会写、但实际调试起来非常关键的经验也一并分享出来。
1. 从零认识排序：到底在解决什么问题？
1.1 排序问题的本质与两个基础分类维度
排序本质上是一个“排列”问题：给定一组元素，按照某种规则（通常是数值大小、字典序、时间先后）重新组织成有序序列。看起来简单，但它背后其实藏着两个永恒的核心约束：比较次数和交换/移动次数。几乎所有排序算法的差异，都体现在如何在两者之间做取舍。
我们可以把所有排序算法按照两个维度快速分类。第一个维度是“是否基于比较”。基于比较的算法，比如冒泡、插入、快速、归并，它们只能通过两两比较来推断顺序；非比较类的算法，比如计数排序、基数排序、桶排序，会利用数据本身的分布特征，在特定场景下能做到线性时间复杂度。第二个维度是“排序过程的稳定性”。稳定排序能保证“值相等的元素在排序后仍保持原来的先后次序”，这一点在业务场景中往往比很多人想象的更重要。我后面会专门展开。
理解这两个维度，不是为了背概念，而是为了帮你建立一种直觉：拿到排序需求时，先不要急着自己造轮子，而是想清楚数据规模、内存限制、是否要求稳定、数据分布是否特殊。这比记住十个算法的代码重要得多。
1.2 为什么“稳定”这个属性经常被大家忽略
稳定性是排序里被忽略最多、却在真实系统中非常关键的性质。举例来说，后台管理系统里常见的“多列排序”需求：先按部门排，再按工号排，如果用的是稳定排序，第一轮按部门排完之后，第二轮按工号排只会调整工号顺序，部门相同的员工之间仍然保持着第一轮的结果顺序。如果换成不稳定排序，第二轮可能会把同部门员工之间的相对顺序完全打乱，看起来就像“排序结果莫名其妙”。
常见的稳定性表现可以用一句话总结：如果两个值相等的元素在排序后互换位置，那这个排序就是不稳定的。选择排序是典型的不稳定排序，快速排序也不稳定；而冒泡、插入、归并都可以做到稳定。
不少从业者在实际开发中依赖数据库的ORDER BY或语言库的排序函数，所以对稳定性没有直观感受。但一旦遇到需要“按多个关键字排序”且不能使用库函数的环境，稳定性就会变成决定成败的细节。希望你在看后续算法细节时，顺手关注一下每个算法的“交换路线”，慢慢就能形成肌肉记忆。
2. 必须先掌握的三种“简单”排序：冒泡、选择、插入
2.1 冒泡排序：最直观，但也最容易在细节上犯错
冒泡排序的核心思路很直白：每一轮从头到尾遍历，把相邻两个元素中“不满足顺序”的交换过来，让最大的元素像气泡一样慢慢“浮”到末尾。冒泡排序的代码门槛低，不过想写得严谨，还是有一些不易察觉的细节。
一个常见的基础实现长这样：
def bubble_sort(arr): n = len(arr) for i in range(n - 1): 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，外层循环执行 n-1 轮，内层循环每轮都在缩小待交换范围。因为第 i 轮结束后，末尾 i 个元素已经有序，不需要再参与排序。
很多人忽略了“提前结束”这个优化。如果某一轮完整遍历后没有发生任何交换，说明数组已经有序，可以直接返回。这在数据近乎有序的场景下，能把平均复杂度从 O(n²) 降到接近 O(n)。
def bubble_sort_optimized(arr): n = len(arr) for i in range(n - 1): 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这个“是否发生过交换”的标记，很多初学者容易漏掉。实际面试或者笔试时，写上这个优化可以体现对排序过程的理解，而不只是机械记忆模板。
再说一个稳定性细节：如果你在代码里写成if arr[j] >= arr[j + 1]，相邻元素相等时也会交换。这样看似无害，实际上已经破坏了稳定性。日常自测时，用一组相同元素的数组就能立刻看出来。我的习惯是：涉及相等的比较，一律只处理“严格大于”或“严格小于”的方向，除非你确实需要某种特殊排序规则。
冒泡排序的主要优势是代码简单、容易证明正确，适合数量很小的数据，比如几十个元素。它的最大劣势是频繁交换，交换本身也是成本，尤其是在移动代价高的场景下，冒泡会非常吃亏。
2.2 选择排序：交换次数最少，但稳定性要小心
选择排序的基本思想是：每一轮从剩余未排序元素里选出最小（或最大）的那个，放到已排序区间的末尾。由于它每轮只需要一次交换，所以整体交换次数非常少，最多只有 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] return arr写选择排序时，最容易犯的错误有两个。一是内层循环的起点写错，导致第一个元素被漏掉；二是找到最小值后忘了判断是否需要交换，如果min_idx等于i，相当于多执行了一次无意义的自交换。
为什么说选择排序不稳定？给你一个经典例子：数组[5, 8, 5, 2]。第一轮找到最小元素是 2，位置在索引 3，于是把它和索引 0 的 5 交换。交换后两个 5 的相对顺序就变了，因为原本在前的 5 去了后面，原本在后的 5 留在了前面。不稳定带来的问题，如果只是排序纯数字，你根本看不出差别，但当你排序的是对象数组，且每个对象有“主排序关键字”和“次排序关键字”时，这种不稳定就可能让结果不符合预期。
选择排序的另一个明显特点是它的时间复杂度永远都是 O(n²)，不管输入数据是否已经有序。这一点和冒泡不同，冒泡在最好情况下经过优化可以变线性，而选择排序每一轮都必须完整扫描剩余区间才能确定最小元素，无法提前结束。
那选择排序什么场景下会用？如果“交换成本”极高，而“比较成本”相对可接受，选择排序就有价值。比如在链表排序中，交换节点代价较大，选择排序只需要改指针，反而可能成为一种不坏的选择。不过大部分通用场景中，它并不算最优解。
2.3 插入排序：近似有序数据的“隐藏冠军”
插入排序的思路可以类比成“理扑克牌”。你从桌上拿起一张牌，把它插到手里已有几张牌的正确位置。具体到数组排序上，从第二个元素开始，逐个向前比较，把大于它的元素往后挪，直到找到合适位置插入。
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插入排序的代码里，最关键的是理解“移动”和“交换”的差别。它不是把 key 和前面元素一个个 swap 过去，而是把前面较大的元素统一向右平移，最后再把 key 放入空出来的位置。这能显著减少赋值次数。
插入排序在“数据基本有序”时表现极好。如果每个元素离它最终位置不远，内层 while 循环很快就能停下来，整体复杂度接近 O(n)。正因如此，很多主流语言的改进排序算法，都会在小规模或近似有序的区间内使用插入排序来收尾。这也是为什么你会在各种“优化版排序”里看到插入排序的影子。
不过，插入排序也有明显的短板：面对大规模乱序数据，它和冒泡、选择一样，老老实实地退化到 O(n²)。所以它适合当“局部瑞士军刀”，而不是主战重型武器。
2.4 三种简单算法的对比与适用场景
简单排序之间并不只是“性能差不多”这么简单，它们各自的边界条件差异很大。我拿一个表格总结一下：
| 算法 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 是否稳定 | 典型优势 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | 稳定 | 代码直观、适合教学和数据量极小场景 |
| 选择排序 | O(n²) | O(n²) | O(n²) | 不稳定 | 交换次数少，适合写代价高昂的场景 |
| 插入排序 | O(n) | O(n²) | O(n²) | 稳定 | 近乎有序数据下性能优秀，增量排序友好 |
选择排序和插入排序的区别往往被忽略。插入排序在最好情况下是 O(n)，选择排序却永远是 O(n²)。所以如果面对一个“可能已经有序，也可能乱序”的输入，插入排序是比选择排序更稳妥的选择。
我在实际的项目里，一般只会在三种情况下手写排序：数据量非常小、数据量特别大有特殊要求、需要用稳定排序且库函数不符合需求。其余情况，优先考虑系统内置的排序函数，因为它们通常融合了多种算法策略，做过大量工程优化。
3. 进入分治世界：快速排序与归并排序
3.1 快速排序：快是快，但基准值别乱选
快速排序是应用最广泛的排序算法之一。它采用“分而治之”的思路：选一个基准值，把比它小的元素放到左边，比它大的放到右边，然后递归排序左右两侧。
经典写法有两种分区方式，我习惯先教 Lomuto 分区法，因为代码更好记：
def quick_sort(arr, left, right): if left >= right: return pivot = arr[right] i = left - 1 for j in range(left, right): if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[right] = arr[right], arr[i + 1] p = i + 1 quick_sort(arr, left, p - 1) quick_sort(arr, p + 1, right)快速排序的平均时间复杂度是 O(n log n)，这也是它受欢迎的主要原因。但它有著名的退化问题：如果每次选的基准值都恰好是当前区间的最小值或最大值，比如对一个已经排好序的数组使用取最后一个元素作为基准的策略，递归深度会变成 n，时间复杂度退化成 O(n²)。我踩过这个坑，当时是一个几乎有序的日志数组，直接导入了快速排序，结果比内置排序慢了几十倍。
避免退化最常见的方案是随机选基准值，或者采用“三数取中”，即从区间首、中、尾三个位置取中间值作为基准。随机化能降低最坏情况出现的概率，三数取中则更稳定，两者结合更好。代码里也可以增加一个“当区间长度小于 10 时改用插入排序”的优化，这和很多底层库的思路是一致的。
快速排序是不稳定排序。如果你需要稳定，同时希望保留 O(n log n) 的平均性能，通常就要考虑归并排序。
3.2 归并排序：稳定性与外部排序的法宝
归并排序的核心也是分治，但它不是靠基准值切分，而是直接对半分，先把左右两个子序列排序，再线性合并。合并时逐个比较两个子序列的头部元素，把较小的先放入结果数组，所以相等的元素可以保持原顺序，天然稳定。
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result归并排序的时间复杂度稳定在 O(n log n)，不受输入影响。代价是需要额外空间，典型实现是 O(n)。这在内存充裕的应用中完全不是问题，但在内存受限的嵌入式环境里，就需要慎重选择。
归并排序最值得一提的是“外部排序”场景。海量数据无法一次性放入内存时，可以利用归并思想，先把数据分成多个小块排序，再逐层归并，每次只加载一部分数据到内存。数据库做大规模排序时，这个思路非常常见。如果你以后碰到“几十 GB 文件需要排序”的需求，第一个想到的应该就是归并而不是快排。
我自己的感受是，归并排序的稳定性和可预测性能非常适合对正确性要求高的场景。比如多个关键字排序、需要保留原始输入次序的报表等，我都愿意优先用归并。
3.3 进阶排序怎么选：一个实用决策表
在实际项目里，我们经常面临的不是“哪个排序最快”，而是“在约束条件下哪个排序最合适”。这里给出一张偏向工程实践的决策表：
| 场景 | 推荐方案 | 理由 |
|---|---|---|
| 数据量小（几十到几百） | 插入排序或内置排序 | 简单、常数小、实现成本低 |
| 数据量中等，无明显极端分布 | 快速排序或内置排序 | 平均性能好，常数小 |
| 要求稳定排序 | 归并排序 | 稳定且性能可预期 |
| 内存非常紧张 | 快速排序变体 | 原地分区，空间占用小 |
| 数据近乎有序 | 插入排序 | 可达到接近 O(n) |
| 数据有大量重复值 | 三路快速排序 | 减少重复元素的多余比较和交换 |
这张表不能替代真实性能测试，但是能帮你一开始就选对方向。项目中的排序方案选型，除了看平均复杂度，还要重点关注输入分布、稳定性要求、内存约束三个维度。
4. 实操经验：排序算法的坑点与调试心得
4.1 典型问题速查表与排查思路
这里列一些我亲眼见过、甚至亲手踩过的排序实现问题，整理成速查表，写代码前后对照检查非常有效：
| 问题现象 | 常见原因 | 排查方法 |
|---|---|---|
| 排序后数组只有一部分有序 | 内外层循环边界写错，导致末尾几个元素没参与 | 打印每一轮结束后的数组，观察排序推进方向 |
| 空数组或单元素数组报错 | 边界条件没有处理，递归或循环直接越界 | 在函数入口对len(arr) <= 1单独返回 |
| 大量相同元素时结果“飘了” | 比较运算符用了>=或<=，破坏了稳定性 | 检查所有比较符号，只对严格大小关系做交换 |
| 已排序数组跑得非常慢 | 快速排序固定选第一个/最后一个做基准值，触发退化 | 加随机基准或三数取中 |
| 递归深度过深导致栈溢出 | 快速排序在接近有序数据上退化出 O(n) 深度 | 换归并排序或改为递归深度限制后的非递归实现 |
| 对象数组排序后字段对不上 | 排序逻辑只比较了部分字段，其他字段没有随元素整体移动 | 排查交换或赋值时是否只操作了比较键 |
我调试排序代码时有一个习惯：永远构造一组“极端输入”再开始跑。极端输入包括空数组、单元素数组、完全倒序数组、已经有序数组、所有元素相同的数组、包含重复元素的数组。这些情况都能快速暴露代码的边界缺陷。我见过很多同事在力扣提交时功能正常，一放到业务数据上就出越界，几乎都是因为只在普通场景下做了测试。
4.2 一次真实对比实验带来的认知更新
有次做日志分析工具，需要在一台配置不高的服务器上对百万级对象做排序。最开始图省事，直接用了手写的快速排序。数据量大，又有大量重复值，结果整体耗时很糟糕。后来换成了内置排序，发现问题马上消失。
这个经验让我意识到两件事。第一，手写排序和库内置排序之间的差距，不只是时间复杂度常数上的微小差别，库函数通常针对缓存友好性、小数组切换策略、重复元素处理等做了大量优化。比如很多语言的sort()底层都是混合策略：数据量小时用插入排序，数据量大时用快速排序或堆排序，检测到递归过深会自动切换堆排序。这些优化不是随手写个快排就能追赶的。
第二，真实性能测试非常重要。为了验证这件事，我后来做了个小实验：生成长度为 10 万、取值随机和取值大量重复的两组数组，分别跑手写快排、内置排序、归并排序。随机数据下手写快排和内置排序差距不算大；重复数据下手写快排明显变慢，而内置排序因为有专门的重复元素处理机制，依然稳定。这就是“理论复杂度”和“工程性能”之间的那层模糊地带。
从那以后，我在项目里的排序方案选型都会遵循一条原则：默认用内置排序，只有明确理由才手写排序算法。手写排序主要用于学习、面试、特殊约束场景，或者作为二次封装的底层组件。
4.3 几个让我少踩坑的细节和习惯
先说一个常见误解：有人觉得“排序算法越快，代码越短”。这个想法很危险。快速排序代码确实短，但因为递归、边界、基准选择等原因，它出问题的概率远高于插入排序。代码短不等于正确率高，遇到性能要求和稳定性要求并存的需求，归并排序的“笨重”反而是优点。
再说说“多次按键排序”的实现。用稳定排序实现多关键字排序时，顺序是“反着的”：先按最不重要的关键字排序，再按次重要关键字排序，最后按最重要关键字排序。比如表格要先按班级排序、再按分数排序，那么你应该先按分数稳定排序，再按班级稳定排序，这样最终班级有序，班级内部分数也有序。这个思路我从一个数据报表需求里踩过坑才记忆深刻。
还有一个细节是“在排序过程中尽量不要修改比较字段”。比如按时间排序时，有人顺手在比较函数里做了字符串格式化，结果每条记录被格式化了好几次，性能骤降。正确的做法是先把所有对象要比较的字段提取成元组，排序一次，再映射回原始对象。排序代码的优化常常不在排序本身，而在入参与比较的预处理。
最后一个习惯是写测试。不只是写完算法之后测试，而是每改一个边界条件就回归一遍。我用过最简单的回归方式是把排序结果和内置排序结果逐项对比。随机生成大量数据，跑一遍手写排序，再用内置排序跑一遍，然后比较两个结果是否完全一致。这套“对拍”方法帮我抓到过不少只在特定数据分布下才暴露的隐蔽问题。
我个人在实际操作中的体会是，学习排序算法不要单纯“背模板”，最好亲手把这个算法的每一步执行过程用纸笔演算一遍。尤其是冒泡、插入、快速三种，把每一轮交换之后的数组状态写出来，对理解指针、索引和递归非常有帮助。排序算法是少有的“看着简单、写好很难”的基础话题，但只要你理解了它们背后的取舍逻辑，再看任何复杂算法都会轻松很多。
