排序算法这块内容我在好几个项目里反复用过也帮别人排查过不少实现上的坑。今天单独把“选择和快排”这两个拎出来写是因为它们正好代表了两条截然不同的思路一个是在原地反复找最小一个是把数组切成两半然后递归处理。理解它们的对比比孤立地背代码有用得多。这两个排序能做什么说白了就是给一组无序数据按从小到大或从大到小排好序。适合谁来读正在学算法的新手、准备笔试面试的开发者、或者在项目里需要手工实现排序而不是直接调用库函数的人。尤其是快排它不仅是性能标杆还是很多语言底层排序的组成部分理解它的分区过程和基准值选择对你排查线上性能问题也有帮助。1. 整体设计与思路拆解1.1 两种思路的碰撞先明确一个基本问题排序问题的输入是一个长度为 n 的数组输出是一个有序数组。看起来简单但不同的算法在“比较次数”“交换次数”“额外空间”“是否稳定”这些维度上差异极大。选择排序的思路是每一轮从未排序区间里挑出最小的元素放到已排序区间的末尾。它属于“暴力枚举”类算法特点是一轮只确定一个元素的最终位置。快排的思路则是分治选一个基准值把数组分成小于基准和大于基准两部分再递归处理左右两侧。它每一轮能同时让多个元素向正确位置靠近效率自然不同。把这两个放在一起对比核心原因在于它们是“O(n²) 迭代思路”和“O(n log n) 分治思路”的典型代表。理解了它们的差别你就理解了为什么算法复杂度的提升不只是常数优化而是思路层面的跃迁。1.2 评价一个排序算法要看什么我习惯用四个维度评价排序算法时间复杂度最好、最坏、平均、空间复杂度、稳定性、数据敏感度。简单解释一下稳定性如果两个相等的元素在排序前后相对顺序不变这个排序就是稳定的。比如按“先分数后姓名”排序的需求里如果第一轮按姓名排第二轮按分数排只有稳定排序才能保证第二轮不会打乱第一轮的结果。选择排序和快排通常都不是稳定排序这一点在业务代码里经常被忽略后面我会展开讲。数据敏感度指的是算法对输入数据顺序的依赖程度。选择排序完全不敏感不管输入是正序、逆序还是乱序比较次数都一样快排则非常敏感遇到某些特定输入会退化这也是实现时最容易踩坑的地方。2. 选择排序最直观的排序思路2.1 算法流程与代码实现选择排序的代码在所有排序里最好写因为思路和代码是一一对应的。核心伪代码如下外层循环从 0 到 n-2每一轮把 i 到末尾区间里的最小值找出来和第 i 个位置交换。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 轮因为最后一轮会剩下两个元素比较一次就完成了最后一个元素自然归位。第二min_idx记录的是索引而不是值因为交换时必须知道位置。我在帮别人 review 代码时见过直接把min_value存下来最后找不到位置的写法这种错误通常只在数据量大时才暴露。交换前加一个if min_idx ! i的判断可以避免不必要的交换操作。这个优化在数组已经基本有序时能省下不少开销虽然不能改变整体的 O(n²) 复杂度但对于数据写入成本高的场景比如写存储介质少一次交换就少一次磨损。2.2 复杂度特征与适用场景选择排序的时间复杂度是稳稳的 O(n²)比较次数恒为 n(n-1)/2不管输入是什么顺序。交换次数最多是 n-1 次这是它的一个隐藏优点——在“比较便宜、交换昂贵”的场景里选择排序反而有优势。举个例子假设你有 1 万条记录每条记录都很长交换一次要复制大量字节。选择排序最多交换 9999 次而冒泡排序在逆序输入下要交换接近 5000 万次。虽然两者都是 O(n²)但实际墙钟时间差距可能是数量级的。不过选择排序的缺点同样明显它不是一个自适应算法对已经排好序的数据依旧要完整跑完所有比较它也不稳定因为一轮交换可能把相等的元素顺序打乱。如果数据规模在几十到几百之间而且你明确知道交换是瓶颈选择排序是一个合理选择数据规模上千以上还是老老实实用快排或者归并。3. 快速排序分治思想的经典实践3.1 分区过程是快排的灵魂快排的每一步都围绕“分区”展开选定一个基准值 pivot把小于它的元素放左边大于它的放右边然后把基准放到中间正确位置。这样一次分区后基准元素就永远不会再动了它左边所有元素都小于它右边所有都大于它。接下来递归处理左右两个子区间即可。分区实现有多种最常见的是 Lomuto 分区和 Hoare 分区。Lomuto 简单直观适合教学Hoare 效率更高交换次数更少但边界条件更隐蔽。我先给一个 Lomuto 的递归实现def quick_sort(arr, low, high): if low high: return 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] pi i 1 quick_sort(arr, low, pi - 1) quick_sort(arr, pi 1, high)这里用数组最后一个元素作为基准值。i维护的是“小于基准区的右边界”j是扫描指针。每发现一个比基准小的元素就把i向右挪一位并交换。扫描结束后i 1就是基准应该待的位置。整个过程本质上是把数组原地重排额外空间只有递归栈。我建议初学者在纸上画一下这个过程用一组小数据比如[5, 3, 8, 1, 4, 7, 2, 6]手推一遍。画完你就会明白为什么交换逻辑长这样而不是死记。3.2 基准值选择的讲究固定选最后一个元素有一个致命问题如果输入本身是升序或降序每轮分区只能分成“一个元素 其余全部元素”递归深度变成 n时间复杂度退化到 O(n²)。我实测过对 10 万个已排序的整数用固定基准的快排耗时会从正常情况的几十毫秒飙升到好几秒递归深度大到直接爆栈都有可能。解决办法按成本从低到高排列随机选基准、三数取中取首、中、尾的中位数、或者更高级的内部采样。最实用的组合是“随机基准 小数组转插入排序”这也是许多标准库的实现思路。import random def quick_sort_random(arr, low, high): if low high: return if high - low 16: # 小区间直接插入排序 for i in range(low 1, high 1): cur arr[i] j i - 1 while j low and arr[j] cur: arr[j 1] arr[j] j - 1 arr[j 1] cur return rand_idx random.randint(low, high) arr[rand_idx], arr[high] arr[high], arr[rand_idx] 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] pi i 1 quick_sort_random(arr, low, pi - 1) quick_sort_random(arr, pi 1, high)high - low 16这个阈值不是拍脑袋定的。插入排序在小区间上常数极小而快排递归栈的建立、函数调用的开销在小区间上相对很大实测在 10 到 20 左右切换最划算。这个数字在不同语言和机器上略有差异你可以自己压测调整。3.3 递归深度、稳定性与复杂度快排的平均时间复杂度是 O(n log n)但这里说的“平均”是有条件的前提是基准值选得足够随机。一旦基准选择有偏性能就不可控。这也是为什么工程实现里几乎不会用固定基准。空间复杂度方面快排是原地排序不需要额外的数组但递归调用会占用栈空间。平均情况下递归深度是 O(log n)最坏是 O(n)。在数据量极大时必须考虑栈溢出的风险。我见过生产环境里因为快排递归过深导致程序崩溃的例子优化手段是“尾递归优化”递归处理较小的子区间较大的子区间用循环继续处理这样能把最坏空间降到 O(log n)。关于稳定性Lomuto 和 Hoare 分区在交换时都可能跨越多个位置相等元素的相对顺序无法保证所以快排是不稳定的。如果你的业务需求明确要求稳定排序不要硬用快排直接选归并排序。4. 两个算法的性能对比与场景选择4.1 关键指标对照把两个算法放在一个表里看更清楚维度选择排序快速排序平均时间复杂度O(n²)O(n log n)最坏时间复杂度O(n²)O(n²)基准选择不当时最好时间复杂度O(n²)O(n log n)空间复杂度O(1)O(log n)平均递归栈稳定性不稳定不稳定数据敏感度不敏感高度敏感交换次数最多 n-1 次平均 O(n log n) 次实现难度低中这张表里最值得关注的是“数据敏感度”这行。选择排序虽然慢但它的慢是“均匀的慢”任何输入都稳定地花 O(n²) 时间不会突然崩溃。快排在平均情况下快得多但遇到构造过的极端输入会退化到和选择排序一样慢甚至因为递归栈开销而更慢。4.2 实际场景里的选择建议我总结了一套简单的选型规则可以直接抄作业数据量小于 50且代码可读性优先用选择排序或插入排序简单不容易错。数据量大、没有稳定性要求用快排配合随机基准和小数组插入排序优化。数据写入成本高交换是瓶颈选择排序的少量交换优势可以派上用场。有稳定性要求别用这两个去用归并排序。数据几乎有序选择排序白给用插入排序能直接享受到 O(n) 的最好情况。还有一个容易忽略的点很多语言标准库的排序函数内部就是混合策略。它们会根据区间大小切换排序算法这正好印证了“没有万能排序只有合适排序”这个道理。理解这些底层实现你在调参和排查性能问题时就不会两眼一抹黑。5. 常见问题与排查技巧实录5.1 快排的边界与退化问题我帮别人排查快排问题时遇到最多的是三类递归死循环、结果错误、性能退化。递归死循环通常是边界条件写错比如递归调用时把pi本身也包含进去或者low high的终止条件写成了low high导致区间长度不为零时无法结束。排查方法很简单在递归函数开头打印low和high看区间长度是否单调递减或者直接设一个最大递归深度超了就抛异常。性能退化最常见的原因是固定基准撞上已排序数据。我做过一个实验对 10 万个随机整数固定基准快排耗时约 0.03 秒对相同数据先排序后再跑耗时飙升到 2 秒以上整整差了接近两个数量级。改用随机基准后即使输入已排序也能稳定在几十毫秒。这个实验建议你自己复现一次感受比看任何文章都深。5.2 选择排序的隐蔽误区选择排序看起来简单但有一个我反复强调的问题稳定性。很多人写了交换逻辑后觉得“我没有移动相等的元素啊”但实际上一次跨距离交换就可能把相等元素的位置关系打乱。比如数组[2a, 2b, 1]第一轮找到最小值 1 并和 2a 交换结果是[1, 2b, 2a]两个 2 的相对顺序就反了。如果业务里依赖稳定性这个细节会直接导致数据错乱。另一个误区是误以为选择排序可以提前终止。选择排序每一轮比较是必须的因为你无法提前知道未排序区间里是不是还有更小的元素。如果你需要“数据接近有序时更快”的算法选择排序满足不了你得用插入排序。还有一个我在实际代码评审里常见的问题把选择排序写成“每一轮都把最小值往前挪”的版本乍一看没问题但实现里多写了大量中间交换导致交换次数从 n-1 变成 O(n²)。这相当于把选择排序最宝贵的优点给丢了性能和冒泡排序一样差代码还更难读。5.3 实测数据与调优心得最后分享一组我在自己机器上的实测数据整数数组单位毫秒数据规模选择排序快排固定基准随机数据快排随机基准10001.80.20.210000681.41.510000061201822100000已排序6120420019这组数据很能说明问题选择排序在数据量过万后基本不可用固定基准快排在随机数据上很漂亮但遇到已排序数据立刻退化随机基准则无论什么输入都稳定。当然不同机器的绝对数值会有差异但量级关系和退化趋势是普遍成立的。我的调优心得是先保证正确性再谈性能。排序代码一定要先用小规模数据和暴力解法对拍验证确认输出正确后再去做基准选择和递归优化。否则你在一个错误实现上做的性能分析毫无意义。对拍验证的方法很简单写一个assert把排序结果和sorted()的结果比对随机生成几百组不同规模的数据跑一遍正确性就有底了。我个人在实际项目中体会最深的一点是理解排序算法不能只停留在“能把数组排好”这个层面。选择排序教会我“减少不必要的操作”有时比“减少比较次数”更关键快排则教会我“最坏情况分析”在工程里不是理论游戏而是真实会发生的灾难。如果你刚开始学这两个算法别急着背代码先手推几组数据、画出分区过程然后自己实现一遍再对拍验证一次这个过程比看几十篇文章都有价值。最后再分享一个排查快排问题的技巧如果你怀疑是基准选择导致退化可以在分区函数里统计每次分区的左右区间长度打印出来看是否有“每次都只分掉一个元素”的情况。如果连续多次出现某个区间长度为 0 或 1说明基准选择有问题优先检查这里通常比瞎调代码快得多。等你能让这个优化版快排扛住“全升序、全降序、全部相等”这三种极端输入你的实现就算真正合格了。
