这些年我带过的团队成员里十个有八个能张口说出冒泡排序、选择排序、插入排序、快速排序的名字但真让他们现场写一个不越界、不写错循环边界的版本能一次通过的并不多。原因倒也不难理解——业务代码里想要排序Python 有sortedJavaScript 有Array.prototype.sortJava 有Collections.sort绝大多数场景一行代码就解决了。但恰恰因为用得太顺手很多人反而错过了这四种排序算法里最值钱的东西它们不只教你怎么排更是在教你怎么分析一个问题、怎么权衡不同方案。这篇文章我就把这四种排序掰开揉碎讲一遍。不只是对着伪代码念而是把每个算法的核心思想、适用场景、边界错误和优化空间都交代清楚顺带分享一些我在调试和面试里反复用到的判断方法。适合刚学算法的人打基础也适合准备面试、或者想系统梳理一遍经典排序的开发者。1. 现在还要不要手写排序——先搞清楚这四种算法的学习价值1.1 内置排序已经足够好为什么还要自己写先说结论日常业务开发中绝大多数情况下你都不需要手写排序直接调用语言内置的排序方法就好。Python的sorted默认采用一种兼顾稳定性和性能的归并排序变体Java对对象数组使用稳定排序、对基本类型数组使用双枢轴快速排序C的标准库std::sort会在多种策略之间切换。这些内置实现是无数人调优过的结果自己写的简单排序在大多数数据规模下完全没法比。那为什么还要自己写三个理由。第一面试要考。不管你是面后端、前端还是数据方向排序几乎是算法面里默认的第一题。面试官不指望你写出一个取代标准库的排序而是想通过这道题观察你的代码基本功循环边界会不会错、递归会不会写、能不能分析出时间复杂度和稳定性。第二理解是调优的前提。内置排序确实好但如果你完全不知道它背后是哪几种策略的组合碰到数据几乎有序、有大量重复元素、用对象某个属性排序这类场景时就只会瞎猜。理解了插入排序和快排的组合逻辑你会一眼看穿内置排序在某些极端输入下的表现。第三也是最容易被忽略的一点排序是理解算法复杂度最直观的载体。同样的一份数据让冒泡跑一跑再让快排跑一跑时间差距是肉眼可见的。复杂度这个概念靠背不可能真正建立感觉亲手实现几种排序之后才会有肌肉记忆。1.2 动手之前先建立比较器思维很多人在写排序时容易掉进一个误区只写对整数数组排序的版本。等面试题换成按对象的某个字段排序就有点懵或者一上来就写嵌套循环把比较逻辑和交换逻辑混在一起。真正的排序无论哪种算法抽取出来其实只做两件事两两比较和按比较结果调整位置。比较这一步最好用一个独立的函数去表达也就是常说的比较器。在 Python 里最简单的做法是给需要排序的每个元素生成一个排序键比如items [(苹果, 3), (香蕉, 1), (橙子, 2)] def price_key(item): return item[1] # 使用示例返回按价格升序排列的新列表 sorted_items sorted(items, keyprice_key)如果必须自定义比较逻辑Python 也提供了functools.cmp_to_key可以把老式的compare(a, b)函数包装成排序键。理解这一点再去看各种排序代码的时候你会发现算法的骨架都是取一个元素、和另一个元素做一次a b或a b判断具体比较的对象到底是不是数字根本不重要。所以在这篇文章里我展示的代码依然以整数排序为主但你心里要清楚只要把中间的arr[j] arr[j 1]换成自定义的比较函数算法逻辑本身完全不需要改动。这是更接近工程实际的理解方式。2. 冒泡与选择双循环里藏着两种相反的思路2.1 冒泡排序相邻对比交换一次把一个最大值浮到末尾冒泡排序的思路是最直观的从数组第一个元素开始两两比较相邻元素如果前一个比后一个大就交换它们。这样一轮下来最大的元素会像气泡一样一路冒到最后面。下一轮再从头开始但不需要再碰最后一个位置因为它已经是整体最大值。一个带提前退出优化的冒泡长这样def bubble_sort(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每次外循环负责确定一个位置的最终值内循环通过相邻交换完成这个任务。swapped这个标志非常关键如果一整轮都没有发生任何交换说明数组已经有序再往后都是浪费直接退出。时间复杂度上最坏情况是一个完全逆序的数组每个元素都要跟相邻元素交换比较次数大约是 n(n-1)/2也就是 O(n²)。最好情况是数组已经有序第一轮扫描完发现没有交换直接结束这时候只需要 n-1 次比较复杂度是 O(n)。平均情况仍然是 O(n²)。2.2 选择排序每次找最小放到开头而不是反复交换选择排序的思路跟冒泡看起来很像都是双重循环但思想其实相反。选择排序每一轮做的事是在未排序的部分里找到最小元素的下标然后把它和未排序部分第一个位置交换。也就是说它不是在相邻元素之间频繁交换而是记账式地扫描一轮找到最小值做一次交换。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内层循环永远在找最小值外层循环把最小值放到正确位置。这个算法最重要的特点是交换次数极少每轮最多一次交换一共最多 n-1 次交换。如果交换两个元素的代价非常昂贵比如元素是体积很大的结构体或者写数据库记录选择排序可能比冒泡更实用。但选择排序有一个比较隐蔽的缺点不稳定。看一个例子数组是[5a, 5b, 1]其中 5a 和 5b 是两个值相等但身份可区分的元素。第一轮扫描找到最小值 1把它和 5a 交换得到[1, 5b, 5a]。两个 5 的相对位置反过来了。后面讲到稳定性的时候这个问题还要展开。2.3 双循环排序最容易踩的边界错误冒泡和选择排序代码量不大但写错的频率出奇地高。我见过最常见的两个错误第一个是内层循环的范围没写对冒泡里把range(n - 1 - i)写成range(n - 1)。这样每一轮都会跑到数组尾部拿已经排好的最大值继续做无意义的比较功能上有时碰巧没错但做了大量重复劳动而且可能把已经排好的部分又搅乱。第二个错误是选择排序的min_idx初始值。有些人喜欢把min_idx初始化为 0 而不是i这在第二轮以后就错了因为 0 位置已经是上一轮选出的最小值不该再参与比较。记住一条原则每轮有效范围是[i, n-1]从i开始找最小才是正确起点。写这类双循环排序最好的方法是先划清不变式再动手。冒泡的不变式是每轮结束后数组末尾 i 个元素是全局最大的 i 个元素且有序。选择排序的不变式是每轮结束后数组开头 i 个元素是有序的且它们都小于等于后面的任何元素。只要两个不变式保持成立代码就不会出现结构性错误。还有一个非常实用的小技巧调试排序算法时不要只看最终结果要在每一轮外循环结束之后打印一次数组状态用一个小样例比如[5, 1, 4, 2, 8]手工推演一遍再对着打印对照。一看循环边界错没错二看交换逻辑对不对。这个方法我第一次是面试前调试时用上的后来带新人做研讨题时也反复提醒比自己盯着代码干想快得多。3. 插入排序被业务代码低估的近乎有序利器3.1 摸牌思路从无序区拿一张往有序区里插插入排序的思路我觉得用扑克牌来解释是最自然的。你打牌的时候整理手牌不是先把整副牌全排序再一张张摆好而是从左到右每拿一张新牌就找它在前面的牌里应该待的位置插进去。已有的牌始终保持有序新牌一进来有序区域就扩大一格。写成代码是这样def insertion_sort(arr): for i in range(1, len(arr)): 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代码里有个细节值得注意这里不是用swap循环交换而是先把当前元素key存到一个临时变量里然后把它前面的、比它大的元素统统往后移一位最后把key放进腾出来的空位。这个移动而不是交换的思路让插入排序在数组上运行时常数非常小。while j 0 and arr[j] key这行是核心。它同时保证了两个条件一是别越界j 不能小于 0二是只有当上一个元素严格大于 key 才继续移动。如果相等就不动所以插入排序是稳定的。3.2 为什么说它被低估很多教材把插入排序和冒泡、选择并列称为低效排序但事实上插入排序在真实场景里的地位远超另外两个。最典型的场景是数据基本有序。假设一个数组大部分元素已经在正确位置只有少数几个错位插入排序的内层循环往往走一两步就停了整体复杂度接近 O(n)而不是 O(n²)。比如一个系统按时间生成的日志序列偶尔有两条时间戳错位你手动用插入排序去整理简直快得飞起。另一个它的大用途是作为更高级排序算法的递归基。快速排序处理很小的子区间时递归调用的开销占比开始变大很多高质量实现会在子数组长度小于某个阈值比如 16 或 32时停止递归改用插入排序收尾。插入排序在短数组上的表现因为常数小、没有递归调用往往反而比快排更快。这是工程中组合拳的一个经典例子我现在看语言内置排序源码时都会特意去确认这种阈值切换每次都有收获。选择排序和冒泡排序虽然代码简单却几乎不会被工程实现选做递归基原因就在于它们在几乎有序的数据上没有任何加速能力。只有插入排序能利用局部有序这个信息。3.3 从插入到二分插入和希尔一点点进阶插入排序有一个明显的改进方向既然它总是要找一个元素在有序区中的插入位置而这个有序区又是已经排序好的为什么不直接用二分查找来找插入点呢这就诞生了二分插入排序。import bisect def binary_insertion_sort(arr): for i in range(1, len(arr)): key arr[i] pos bisect.bisect_right(arr, key, 0, i) for j in range(i, pos, -1): arr[j] arr[j - 1] arr[pos] key return arr注意二分查找把找位置那一步从 O(i) 降到了 O(log i)但腾位置这一步仍然需要把后面的元素集体后移 O(i) 次。所以二分插入排序的时间复杂度依然是 O(n²)只是常数变小了。这说明一个很重要的道理排序的瓶颈往往不在于比较而在于元素的移动。再往前走一步如果允许跨过较远的距离进行插入就变成了希尔排序。希尔排序的核心是按间隔分组做插入排序逐步缩小间隔。它打破了每次只交换相邻元素的限制让元素能快速跳跃到大致正确的位置。希尔排序是现代教材里通常排在插入排序之后的第一个看起来不太复杂但效果显著的排序序列选择得好的时候复杂度可以降到 O(n^1.3) 左右。我建议学完插入排序后顺手写一遍希尔排序你会更强烈地感受到把有序性逐步扩大这件事有多强大。4. 快速排序平均最快的算法也是最容易写错的那个4.1 分治思想和 partition 的分区逻辑快速排序是四种里面唯一使用递归和分治思想的。它的核心操作叫partition分区从数组里选一个基准值pivot把比基准值小的元素放到左边比基准值大的放到右边等于基准值的放中间哪个位置看实现。一趟分区之后基准值就已经落在了它最终该在的位置上。然后对基准值左边和右边两个子数组分别递归执行同样的操作直到子数组长度小于等于 1。因为每次分区都能至少确定一个元素的最终位置递归下去整个数组就有序了。我用 Python 实现一个最通用的版本采用Lomuto 分区基准值取当前区间最右边的元素def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) # 排序基准值左边 quick_sort(arr, pi 1, high) # 排序基准值右边 return arr def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1分区的过程可以想象成维护一条分界线。变量i指向的是最后一个比基准值小的元素位置j从头到尾扫描每发现一个比基准值小的元素就把分界线前进一格并把这个小元素换到分界线左边。扫描结束后把基准值放到分界线后面就是它的最终位置。4.2 一大坑你以为的快排是切片版网上很多教程会把快排写成一个让人眼前一亮的短版本def quick_sort_concise(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort_concise(left) middle quick_sort_concise(right)这个写法是不是很熟悉它确实能排序而且思路也确实是分治但它有两个在工程中很要命的问题。第一每次递归都创建三个新列表空间复杂度是 O(n log n)而不是原地快排的 O(log n)。数据量一大内存会迅速被撑爆。第二它丢失了快排原地修改数组的意义。很多真实场景里你不想额外复制一大份数据而是希望直接在原数组上交换位置。所以在面试和实际项目中请写原地分区版本。考试卷面上那种三行快排看起来漂亮但一追问空间复杂度就露馅了。顺带说一句Lomuto 分区虽然好写但有一个小弱点当数组里存在大量重复元素时它会把相等的元素全部归到某一侧递归深度变差。如果在面试中被问到如何优化可以提三路快排的思路把数组分成小于基准值、等于基准值、大于基准值三部分只对小于和大于的部分递归。经典的荷兰国旗问题就是这种分区的模板。4.3 快排最坏情况顺序数组、逆序数组和基准值选择快排之所以平均最快是因为它平均情况下能把问题规模减半递归树高度约为 log n每层做 O(n) 的分区工作总复杂度 O(n log n)。但注意这只是平均。最坏情况下快排会退化成 O(n²)。最经典的反例是对一个已经排好序的数组每次都取最后一个元素作为基准值。这时分区结果是极度不平衡的左边有 n-1 个元素右边 0 个递归树变成一条链做满 n 次递归性能还不如插入排序。解决办法有三个层次。最简单的是随机化基准值每次从low到high随机选一个位置和末尾交换保证输入顺序与基准值无关。稍微进阶一点的是三数取中从区间头部、中间、尾部取三个元素用它们的中位数作为基准值。这样可以明显降低遇到最坏情况的概率。第三个层次是之前提过的阈值切换在递归到很短的子数组时停止递归改用插入排序。我自己曾经在一次批量排序任务里给一个几乎完全有序的大表用快排当时偷懒没随机化基准值结果眼睁睁看着它在几万条数据上跑了将近一分钟而换用内置排序是毫秒级。那次之后我养成了一个习惯手感再好也要在排序入口显式地随机化基准值这是用一行代码买一份保障。另一个容易忽略的坑是递归深度。快排平均递归深度 O(log n)但最坏情况递归深度 O(n)在递归深度受限制的语言环境里这可能直接导致调用栈溢出。工程上有很多避免递归的写法比如把递归改成显式栈或者优先递归较短的子区间以控制最大递归深度。4.4 稳定性问题为什么快排不稳定快排和选择排序一样是不稳定排序。原因出在分区过程中的交换。举一个简单例子数组[3a, 3b, 1]取最右侧的 1 作为基准值。扫描时第一个元素 3a 不小于 1不动第二个 3b 不小于 1不动i仍然是 low-1。分区结束以后基准值 1 和arr[i1]也就是arr[0]3a交换位置得到[1, 3b, 3a]。两个 3 的相对顺序又反了。这里的本质原因是分区里的交换并不限于相邻元素而是可能跨越较远的距离直接交换相等元素之间的相对顺序无法保证。理解了这一点你就不需要死记快排不稳定因为它本来就是为速度牺牲稳定性的典型代表。5. 四者对比复杂度、稳定性与真实场景选型5.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 log n)O(n log n)O(n²)O(log n)不稳定平均性能最优工程中使用最广这张表里我最想提醒的一点是最好情况插入排序是 O(n)冒泡排序也是 O(n)但选择排序永远是 O(n²)。很多人背复杂度的时候容易把三种 O(n²) 的排序一锅端这其实不对选择排序即使数据完全有序也必须做完整扫描才能确定最小值。理解这个区别才能在这个数组基本已经排好了的场景里做出正确判断。5.2 稳定性在业务中的真实价值很多初学者觉得稳定性是个虚无缥缈的属性面试考完就扔。但在真实业务里稳定性有非常具体的用处尤其是分阶段排序的场景。举一个报表系统常见的需求有一批任务记录每个记录有所属部门和紧急程度两个字段。现在希望展示的时候紧急程度高的一定排前面紧急程度相同的保持部门顺序也就是先按部门排好再按紧急程度排。如果第一次先按紧急程度排序第二次再按部门排序第二次排序若用的是不稳定排序就可能把同部门内部原本按紧急程度排好的顺序打乱。反过来做先按部门稳定排序再按紧急程度稳定排序这样紧急程度相同的记录之间部门顺序被保留了。英文通信里常说 stable sort preserves the relative order of equal elements翻译过来就是相等的元素稳定的排序不会乱动它们原来的先后。判断一个算法稳不稳定最简单的测试方法就是构造两个相等元素并打上不同记号看排序后记号顺序是否改变。冒泡和插入稳定选择和快排不稳定这个结论直接对应到分阶段排序场景的选型上。5.3 实战选型心法真到了项目的选择环节我的判断顺序一般是这样的。数据量小比如几十个元素直接插入排序或内置排序差别肉眼根本看不出来。数据量中等比如几百到几千且明确知道数据接近有序插入排序表现很好一个 O(n) 就能完事。数据量大且随机性强又需要考虑空间优先用快排优化版记得加随机化基准值。如果对稳定性有硬性要求比如上面的分阶段排序场景快排就不合适应该选择归并排序这样稳定的 O(n log n) 算法代价是要额外 O(n) 空间。我在本地随手测过一组数据给长度为 10000 的随机整数数组排序冒泡和选择在几个量级的耗时明显感人插入排序好一些但仍然不够快快排则基本是毫秒级完成。如果改成近乎有序的数据插入排序直接反超选择排序一大截。这种横向对比建议你也亲自动手跑一次复杂度从纸面落到眼前印象会深得多。还有一个小经验真正在生产环境里绝大多数时候还是直接用内置排序最省心。手写这四种排序的价值在于理解不在于替代。内置排序已经把分治、递归基、稳定排序、过度到插入排序这些事情全部封装好了。你要是能看懂内置排序为什么在大数组和小数组之间切换策略、为什么在某些语言里保持稳定而在另一些语言里不保证那对排序的理解就已经超过大多数只会调 API 的人了。写到这里我还是想强调那句话排序算法的价值不只在能排更在它逼着你把循环边界、递归栈、复杂度、稳定性这些东西全部过一遍脑子。我自己的体会是学这几类排序最有用的收获不是代码而是写任何逻辑前先想清楚不变式的习惯。你也不妨在本地跑一跑这四份代码每轮打印一次数组状态让每种排序的轨迹在脑子里留下动画一样的印象。这样以后不管是改数据、做评测还是面试压题看到排序两个字你心里都会比较有底气。
这些年我带过的团队成员里十个有八个能张口说出冒泡排序、选择排序、插入排序、快速排序的名字但真让他们现场写一个不越界、不写错循环边界的版本能一次通过的并不多。原因倒也不难理解——业务代码里想要排序Python 有sortedJavaScript 有Array.prototype.sortJava 有Collections.sort绝大多数场景一行代码就解决了。但恰恰因为用得太顺手很多人反而错过了这四种排序算法里最值钱的东西它们不只教你怎么排更是在教你怎么分析一个问题、怎么权衡不同方案。这篇文章我就把这四种排序掰开揉碎讲一遍。不只是对着伪代码念而是把每个算法的核心思想、适用场景、边界错误和优化空间都交代清楚顺带分享一些我在调试和面试里反复用到的判断方法。适合刚学算法的人打基础也适合准备面试、或者想系统梳理一遍经典排序的开发者。1. 现在还要不要手写排序——先搞清楚这四种算法的学习价值1.1 内置排序已经足够好为什么还要自己写先说结论日常业务开发中绝大多数情况下你都不需要手写排序直接调用语言内置的排序方法就好。Python的sorted默认采用一种兼顾稳定性和性能的归并排序变体Java对对象数组使用稳定排序、对基本类型数组使用双枢轴快速排序C的标准库std::sort会在多种策略之间切换。这些内置实现是无数人调优过的结果自己写的简单排序在大多数数据规模下完全没法比。那为什么还要自己写三个理由。第一面试要考。不管你是面后端、前端还是数据方向排序几乎是算法面里默认的第一题。面试官不指望你写出一个取代标准库的排序而是想通过这道题观察你的代码基本功循环边界会不会错、递归会不会写、能不能分析出时间复杂度和稳定性。第二理解是调优的前提。内置排序确实好但如果你完全不知道它背后是哪几种策略的组合碰到数据几乎有序、有大量重复元素、用对象某个属性排序这类场景时就只会瞎猜。理解了插入排序和快排的组合逻辑你会一眼看穿内置排序在某些极端输入下的表现。第三也是最容易被忽略的一点排序是理解算法复杂度最直观的载体。同样的一份数据让冒泡跑一跑再让快排跑一跑时间差距是肉眼可见的。复杂度这个概念靠背不可能真正建立感觉亲手实现几种排序之后才会有肌肉记忆。1.2 动手之前先建立比较器思维很多人在写排序时容易掉进一个误区只写对整数数组排序的版本。等面试题换成按对象的某个字段排序就有点懵或者一上来就写嵌套循环把比较逻辑和交换逻辑混在一起。真正的排序无论哪种算法抽取出来其实只做两件事两两比较和按比较结果调整位置。比较这一步最好用一个独立的函数去表达也就是常说的比较器。在 Python 里最简单的做法是给需要排序的每个元素生成一个排序键比如items [(苹果, 3), (香蕉, 1), (橙子, 2)] def price_key(item): return item[1] # 使用示例返回按价格升序排列的新列表 sorted_items sorted(items, keyprice_key)如果必须自定义比较逻辑Python 也提供了functools.cmp_to_key可以把老式的compare(a, b)函数包装成排序键。理解这一点再去看各种排序代码的时候你会发现算法的骨架都是取一个元素、和另一个元素做一次a b或a b判断具体比较的对象到底是不是数字根本不重要。所以在这篇文章里我展示的代码依然以整数排序为主但你心里要清楚只要把中间的arr[j] arr[j 1]换成自定义的比较函数算法逻辑本身完全不需要改动。这是更接近工程实际的理解方式。2. 冒泡与选择双循环里藏着两种相反的思路2.1 冒泡排序相邻对比交换一次把一个最大值浮到末尾冒泡排序的思路是最直观的从数组第一个元素开始两两比较相邻元素如果前一个比后一个大就交换它们。这样一轮下来最大的元素会像气泡一样一路冒到最后面。下一轮再从头开始但不需要再碰最后一个位置因为它已经是整体最大值。一个带提前退出优化的冒泡长这样def bubble_sort(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每次外循环负责确定一个位置的最终值内循环通过相邻交换完成这个任务。swapped这个标志非常关键如果一整轮都没有发生任何交换说明数组已经有序再往后都是浪费直接退出。时间复杂度上最坏情况是一个完全逆序的数组每个元素都要跟相邻元素交换比较次数大约是 n(n-1)/2也就是 O(n²)。最好情况是数组已经有序第一轮扫描完发现没有交换直接结束这时候只需要 n-1 次比较复杂度是 O(n)。平均情况仍然是 O(n²)。2.2 选择排序每次找最小放到开头而不是反复交换选择排序的思路跟冒泡看起来很像都是双重循环但思想其实相反。选择排序每一轮做的事是在未排序的部分里找到最小元素的下标然后把它和未排序部分第一个位置交换。也就是说它不是在相邻元素之间频繁交换而是记账式地扫描一轮找到最小值做一次交换。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内层循环永远在找最小值外层循环把最小值放到正确位置。这个算法最重要的特点是交换次数极少每轮最多一次交换一共最多 n-1 次交换。如果交换两个元素的代价非常昂贵比如元素是体积很大的结构体或者写数据库记录选择排序可能比冒泡更实用。但选择排序有一个比较隐蔽的缺点不稳定。看一个例子数组是[5a, 5b, 1]其中 5a 和 5b 是两个值相等但身份可区分的元素。第一轮扫描找到最小值 1把它和 5a 交换得到[1, 5b, 5a]。两个 5 的相对位置反过来了。后面讲到稳定性的时候这个问题还要展开。2.3 双循环排序最容易踩的边界错误冒泡和选择排序代码量不大但写错的频率出奇地高。我见过最常见的两个错误第一个是内层循环的范围没写对冒泡里把range(n - 1 - i)写成range(n - 1)。这样每一轮都会跑到数组尾部拿已经排好的最大值继续做无意义的比较功能上有时碰巧没错但做了大量重复劳动而且可能把已经排好的部分又搅乱。第二个错误是选择排序的min_idx初始值。有些人喜欢把min_idx初始化为 0 而不是i这在第二轮以后就错了因为 0 位置已经是上一轮选出的最小值不该再参与比较。记住一条原则每轮有效范围是[i, n-1]从i开始找最小才是正确起点。写这类双循环排序最好的方法是先划清不变式再动手。冒泡的不变式是每轮结束后数组末尾 i 个元素是全局最大的 i 个元素且有序。选择排序的不变式是每轮结束后数组开头 i 个元素是有序的且它们都小于等于后面的任何元素。只要两个不变式保持成立代码就不会出现结构性错误。还有一个非常实用的小技巧调试排序算法时不要只看最终结果要在每一轮外循环结束之后打印一次数组状态用一个小样例比如[5, 1, 4, 2, 8]手工推演一遍再对着打印对照。一看循环边界错没错二看交换逻辑对不对。这个方法我第一次是面试前调试时用上的后来带新人做研讨题时也反复提醒比自己盯着代码干想快得多。3. 插入排序被业务代码低估的近乎有序利器3.1 摸牌思路从无序区拿一张往有序区里插插入排序的思路我觉得用扑克牌来解释是最自然的。你打牌的时候整理手牌不是先把整副牌全排序再一张张摆好而是从左到右每拿一张新牌就找它在前面的牌里应该待的位置插进去。已有的牌始终保持有序新牌一进来有序区域就扩大一格。写成代码是这样def insertion_sort(arr): for i in range(1, len(arr)): 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代码里有个细节值得注意这里不是用swap循环交换而是先把当前元素key存到一个临时变量里然后把它前面的、比它大的元素统统往后移一位最后把key放进腾出来的空位。这个移动而不是交换的思路让插入排序在数组上运行时常数非常小。while j 0 and arr[j] key这行是核心。它同时保证了两个条件一是别越界j 不能小于 0二是只有当上一个元素严格大于 key 才继续移动。如果相等就不动所以插入排序是稳定的。3.2 为什么说它被低估很多教材把插入排序和冒泡、选择并列称为低效排序但事实上插入排序在真实场景里的地位远超另外两个。最典型的场景是数据基本有序。假设一个数组大部分元素已经在正确位置只有少数几个错位插入排序的内层循环往往走一两步就停了整体复杂度接近 O(n)而不是 O(n²)。比如一个系统按时间生成的日志序列偶尔有两条时间戳错位你手动用插入排序去整理简直快得飞起。另一个它的大用途是作为更高级排序算法的递归基。快速排序处理很小的子区间时递归调用的开销占比开始变大很多高质量实现会在子数组长度小于某个阈值比如 16 或 32时停止递归改用插入排序收尾。插入排序在短数组上的表现因为常数小、没有递归调用往往反而比快排更快。这是工程中组合拳的一个经典例子我现在看语言内置排序源码时都会特意去确认这种阈值切换每次都有收获。选择排序和冒泡排序虽然代码简单却几乎不会被工程实现选做递归基原因就在于它们在几乎有序的数据上没有任何加速能力。只有插入排序能利用局部有序这个信息。3.3 从插入到二分插入和希尔一点点进阶插入排序有一个明显的改进方向既然它总是要找一个元素在有序区中的插入位置而这个有序区又是已经排序好的为什么不直接用二分查找来找插入点呢这就诞生了二分插入排序。import bisect def binary_insertion_sort(arr): for i in range(1, len(arr)): key arr[i] pos bisect.bisect_right(arr, key, 0, i) for j in range(i, pos, -1): arr[j] arr[j - 1] arr[pos] key return arr注意二分查找把找位置那一步从 O(i) 降到了 O(log i)但腾位置这一步仍然需要把后面的元素集体后移 O(i) 次。所以二分插入排序的时间复杂度依然是 O(n²)只是常数变小了。这说明一个很重要的道理排序的瓶颈往往不在于比较而在于元素的移动。再往前走一步如果允许跨过较远的距离进行插入就变成了希尔排序。希尔排序的核心是按间隔分组做插入排序逐步缩小间隔。它打破了每次只交换相邻元素的限制让元素能快速跳跃到大致正确的位置。希尔排序是现代教材里通常排在插入排序之后的第一个看起来不太复杂但效果显著的排序序列选择得好的时候复杂度可以降到 O(n^1.3) 左右。我建议学完插入排序后顺手写一遍希尔排序你会更强烈地感受到把有序性逐步扩大这件事有多强大。4. 快速排序平均最快的算法也是最容易写错的那个4.1 分治思想和 partition 的分区逻辑快速排序是四种里面唯一使用递归和分治思想的。它的核心操作叫partition分区从数组里选一个基准值pivot把比基准值小的元素放到左边比基准值大的放到右边等于基准值的放中间哪个位置看实现。一趟分区之后基准值就已经落在了它最终该在的位置上。然后对基准值左边和右边两个子数组分别递归执行同样的操作直到子数组长度小于等于 1。因为每次分区都能至少确定一个元素的最终位置递归下去整个数组就有序了。我用 Python 实现一个最通用的版本采用Lomuto 分区基准值取当前区间最右边的元素def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) # 排序基准值左边 quick_sort(arr, pi 1, high) # 排序基准值右边 return arr def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1分区的过程可以想象成维护一条分界线。变量i指向的是最后一个比基准值小的元素位置j从头到尾扫描每发现一个比基准值小的元素就把分界线前进一格并把这个小元素换到分界线左边。扫描结束后把基准值放到分界线后面就是它的最终位置。4.2 一大坑你以为的快排是切片版网上很多教程会把快排写成一个让人眼前一亮的短版本def quick_sort_concise(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort_concise(left) middle quick_sort_concise(right)这个写法是不是很熟悉它确实能排序而且思路也确实是分治但它有两个在工程中很要命的问题。第一每次递归都创建三个新列表空间复杂度是 O(n log n)而不是原地快排的 O(log n)。数据量一大内存会迅速被撑爆。第二它丢失了快排原地修改数组的意义。很多真实场景里你不想额外复制一大份数据而是希望直接在原数组上交换位置。所以在面试和实际项目中请写原地分区版本。考试卷面上那种三行快排看起来漂亮但一追问空间复杂度就露馅了。顺带说一句Lomuto 分区虽然好写但有一个小弱点当数组里存在大量重复元素时它会把相等的元素全部归到某一侧递归深度变差。如果在面试中被问到如何优化可以提三路快排的思路把数组分成小于基准值、等于基准值、大于基准值三部分只对小于和大于的部分递归。经典的荷兰国旗问题就是这种分区的模板。4.3 快排最坏情况顺序数组、逆序数组和基准值选择快排之所以平均最快是因为它平均情况下能把问题规模减半递归树高度约为 log n每层做 O(n) 的分区工作总复杂度 O(n log n)。但注意这只是平均。最坏情况下快排会退化成 O(n²)。最经典的反例是对一个已经排好序的数组每次都取最后一个元素作为基准值。这时分区结果是极度不平衡的左边有 n-1 个元素右边 0 个递归树变成一条链做满 n 次递归性能还不如插入排序。解决办法有三个层次。最简单的是随机化基准值每次从low到high随机选一个位置和末尾交换保证输入顺序与基准值无关。稍微进阶一点的是三数取中从区间头部、中间、尾部取三个元素用它们的中位数作为基准值。这样可以明显降低遇到最坏情况的概率。第三个层次是之前提过的阈值切换在递归到很短的子数组时停止递归改用插入排序。我自己曾经在一次批量排序任务里给一个几乎完全有序的大表用快排当时偷懒没随机化基准值结果眼睁睁看着它在几万条数据上跑了将近一分钟而换用内置排序是毫秒级。那次之后我养成了一个习惯手感再好也要在排序入口显式地随机化基准值这是用一行代码买一份保障。另一个容易忽略的坑是递归深度。快排平均递归深度 O(log n)但最坏情况递归深度 O(n)在递归深度受限制的语言环境里这可能直接导致调用栈溢出。工程上有很多避免递归的写法比如把递归改成显式栈或者优先递归较短的子区间以控制最大递归深度。4.4 稳定性问题为什么快排不稳定快排和选择排序一样是不稳定排序。原因出在分区过程中的交换。举一个简单例子数组[3a, 3b, 1]取最右侧的 1 作为基准值。扫描时第一个元素 3a 不小于 1不动第二个 3b 不小于 1不动i仍然是 low-1。分区结束以后基准值 1 和arr[i1]也就是arr[0]3a交换位置得到[1, 3b, 3a]。两个 3 的相对顺序又反了。这里的本质原因是分区里的交换并不限于相邻元素而是可能跨越较远的距离直接交换相等元素之间的相对顺序无法保证。理解了这一点你就不需要死记快排不稳定因为它本来就是为速度牺牲稳定性的典型代表。5. 四者对比复杂度、稳定性与真实场景选型5.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 log n)O(n log n)O(n²)O(log n)不稳定平均性能最优工程中使用最广这张表里我最想提醒的一点是最好情况插入排序是 O(n)冒泡排序也是 O(n)但选择排序永远是 O(n²)。很多人背复杂度的时候容易把三种 O(n²) 的排序一锅端这其实不对选择排序即使数据完全有序也必须做完整扫描才能确定最小值。理解这个区别才能在这个数组基本已经排好了的场景里做出正确判断。5.2 稳定性在业务中的真实价值很多初学者觉得稳定性是个虚无缥缈的属性面试考完就扔。但在真实业务里稳定性有非常具体的用处尤其是分阶段排序的场景。举一个报表系统常见的需求有一批任务记录每个记录有所属部门和紧急程度两个字段。现在希望展示的时候紧急程度高的一定排前面紧急程度相同的保持部门顺序也就是先按部门排好再按紧急程度排。如果第一次先按紧急程度排序第二次再按部门排序第二次排序若用的是不稳定排序就可能把同部门内部原本按紧急程度排好的顺序打乱。反过来做先按部门稳定排序再按紧急程度稳定排序这样紧急程度相同的记录之间部门顺序被保留了。英文通信里常说 stable sort preserves the relative order of equal elements翻译过来就是相等的元素稳定的排序不会乱动它们原来的先后。判断一个算法稳不稳定最简单的测试方法就是构造两个相等元素并打上不同记号看排序后记号顺序是否改变。冒泡和插入稳定选择和快排不稳定这个结论直接对应到分阶段排序场景的选型上。5.3 实战选型心法真到了项目的选择环节我的判断顺序一般是这样的。数据量小比如几十个元素直接插入排序或内置排序差别肉眼根本看不出来。数据量中等比如几百到几千且明确知道数据接近有序插入排序表现很好一个 O(n) 就能完事。数据量大且随机性强又需要考虑空间优先用快排优化版记得加随机化基准值。如果对稳定性有硬性要求比如上面的分阶段排序场景快排就不合适应该选择归并排序这样稳定的 O(n log n) 算法代价是要额外 O(n) 空间。我在本地随手测过一组数据给长度为 10000 的随机整数数组排序冒泡和选择在几个量级的耗时明显感人插入排序好一些但仍然不够快快排则基本是毫秒级完成。如果改成近乎有序的数据插入排序直接反超选择排序一大截。这种横向对比建议你也亲自动手跑一次复杂度从纸面落到眼前印象会深得多。还有一个小经验真正在生产环境里绝大多数时候还是直接用内置排序最省心。手写这四种排序的价值在于理解不在于替代。内置排序已经把分治、递归基、稳定排序、过度到插入排序这些事情全部封装好了。你要是能看懂内置排序为什么在大数组和小数组之间切换策略、为什么在某些语言里保持稳定而在另一些语言里不保证那对排序的理解就已经超过大多数只会调 API 的人了。写到这里我还是想强调那句话排序算法的价值不只在能排更在它逼着你把循环边界、递归栈、复杂度、稳定性这些东西全部过一遍脑子。我自己的体会是学这几类排序最有用的收获不是代码而是写任何逻辑前先想清楚不变式的习惯。你也不妨在本地跑一跑这四份代码每轮打印一次数组状态让每种排序的轨迹在脑子里留下动画一样的印象。这样以后不管是改数据、做评测还是面试压题看到排序两个字你心里都会比较有底气。
