1. 排序算法到底在排什么先把“比较”这件事聊透很多人学排序一上来就背代码背完快排背归并背完归并背堆排结果面试被问一句“为什么快排最坏是 O(n²) 却还叫快排”就卡住了。我自己当年也是这样后来带过几个刚入行的朋友发现大家卡住的地方几乎一模一样不是不会写而是没搞明白排序算法到底在“比”什么、为什么有的快有的慢、什么时候该用哪个。先把最核心的一件事说清楚绝大多数经典排序算法本质上都在做同一件事——通过比较两个元素的大小来决定它们的相对顺序。这类算法统称为基于比较的排序。冒泡、插入、选择、希尔、归并、快排、堆排全都属于这一类。它们有一个共同的理论天花板任何基于比较的排序最坏情况下至少需要 O(n log n) 次比较。这不是某个算法不够聪明而是数学上证明死的下界。为什么是 n log n你可以这样理解n 个元素一共有 n! 种排列可能每次比较最多只能把可能性砍成两半所以至少需要 log₂(n!) 次比较才能区分出唯一正确的顺序。而 log₂(n!) 约等于 n log n。这个结论很重要它告诉你当你看到某个基于比较的排序号称平均比 O(n log n) 还快那基本可以判定要么是特定数据下的巧合要么是描述有问题。那有没有突破这个天花板的有就是非比较排序比如计数排序、桶排序、基数排序。它们不靠“比大小”而是靠元素本身的数值特征比如范围、位数直接定位。代价是适用条件很苛刻计数排序要求数据范围小且是整数基数排序要求能按位拆分。所以它们不是“更高级的排序”而是“在特定场景下更合适的排序”。我习惯把排序算法分成三档来理解这个分法对我带人特别有用档次代表算法平均时间复杂度典型适用场景入门档冒泡、插入、选择O(n²)教学、小规模数据、近乎有序的数据实用档快排、归并、堆排O(n log n)通用排序、面试高频、工程默认选择特化档计数、桶、基数O(nk) 级别整数、范围有限、外部排序这张表你先记住后面每一节我都会把里面的算法拆开讲。但记住一点没有“最好的排序算法”只有“最适合当前数据的排序算法”。这句话不是套话等你踩过几次坑就会深有体会。2. 三个 O(n²) 算法别看不起它们插入排序在工程里活得好好的2.1 冒泡排序为什么它几乎只存在于教材里冒泡排序的逻辑特别直观从头到尾两两比较大的往后挪一轮下来最大的就“冒”到了末尾重复 n 轮就排好了。代码短到可以背下来但它的效率实在感人。我实测过一组数据对 10000 个随机整数排序冒泡在我的机器上跑了将近 300 毫秒而快排只用了不到 2 毫秒。差了上百倍。原因在于冒泡的交换次数太多每一轮都要反复搬运元素缓存友好性也差。不过冒泡有一个“优化版”值得提一句如果某一轮没有发生任何交换说明已经有序可以提前退出。这个优化让冒泡在近乎有序的数据上表现不错接近 O(n)。但即便如此插入排序在同样场景下还是更快所以冒泡的实用价值确实很低。我的建议冒泡排序用来理解“比较与交换”这个基本模型就够了真正写业务代码时不要用它。面试如果被要求手写写优化版能加分。2.2 插入排序小数组和近乎有序数据的王者插入排序的思路像打扑克摸牌左手是已排好的牌右手摸到一张新牌从右往左找位置插进去。它的平均复杂度是 O(n²)但在两种场景下表现极好数据规模很小比如 n 16此时 O(n²) 的常数因子小反而比快排的递归开销更划算。数据近乎有序每个元素只需要移动很少的位置接近 O(n)。这不是纸上谈兵。很多工业级排序库比如某些标准库的排序实现在递归到小数组时会切换成插入排序而不是继续递归。原因就是上面这两点。我自己写过一个简易的通用排序函数当子数组长度小于 16 时改用插入排序整体性能比纯快排提升了大概 10% 到 15%。插入排序还有一个隐藏优点它是稳定的。所谓稳定就是相等元素的相对顺序在排序后保持不变。这个性质在按多个字段排序时非常关键后面讲归并的时候我会展开。2.3 选择排序交换次数最少但比较次数一次都省不了选择排序每一轮从未排序区间里挑出最小的放到已排序区间的末尾。它的特点是交换次数最少最多 n-1 次交换。如果你排序的元素很大比如每个元素是一个大对象交换成本很高选择排序的交换优势就体现出来了。但它的比较次数固定是 n(n-1)/2不管数据是否有序一次都省不了。所以它在近乎有序的数据上没有任何优势反而不如插入排序。我一般只在“交换成本极高、比较成本极低”的特殊场景才会考虑它日常几乎用不到。这三个 O(n²) 算法放在一起对比结论很清楚算法最好情况最坏情况稳定性交换次数冒泡O(n)优化版O(n²)稳定多插入O(n)O(n²)稳定中等选择O(n²)O(n²)不稳定最少实操心得如果你要排序的数据量小于 20 且基本有序直接用插入排序别犹豫。这个判断我在实际项目里用过很多次屡试不爽。3. 快排平均最快但你必须知道它什么时候会“翻车”3.1 快排的核心不是“快”而是“分”快速排序的名字容易让人误解以为它有什么魔法。其实它的核心思想就两个字分治。选一个基准值pivot把数组分成“比基准小”和“比基准大”两部分然后对两部分递归排序。快排之所以平均快是因为它的常数因子小而且分区过程对 CPU 缓存非常友好——它是在原地来回扫描不像归并需要额外开数组。我做过一个粗略的基准测试同样是 100 万个随机整数快排比归并快大约 20% 到 30%主要赢在内存访问模式上。但快排有一个致命弱点基准值选得不好会退化成 O(n²)。最典型的情况是数组已经有序而你每次都选第一个元素当基准。这时候每次分区只能分出一个元素递归深度变成 n复杂度直接爆炸。3.2 基准值选择的三种策略与实测对比怎么避免退化关键在基准值的选择。常见有三种策略固定选第一个或最后一个最简单但在有序数据上必退化。不推荐。随机选一个用随机数决定基准期望复杂度是 O(n log n)。实现简单效果稳定。三数取中取首、中、尾三个元素的中位数作为基准。这个策略在近乎有序的数据上表现很好而且不需要随机数生成的开销。我实测过这三种策略在“完全有序的 10 万整数”上的表现固定选第一个直接卡死跑了十几秒没出来随机选和三数取中都在几十毫秒内完成。所以工程上要么随机要么三数取中千万别固定选端点。还有一个工程技巧小区间切换插入排序。当递归的子数组长度小于某个阈值常见是 8 到 16改用插入排序。这个优化能减少大量递归调用开销实测提升 10% 以上。3.3 快排的稳定性问题与三路分区快排是不稳定的。分区过程中相等元素可能被交换到不同位置。如果你需要稳定排序快排不是好选择。另外当数组中有大量重复元素时普通的两路分区会把所有等于基准的元素分到同一侧导致分区极度不平衡。解决办法是三路分区把数组分成“小于”“等于”“大于”三段等于基准的那段就不用再递归了。这个优化在重复元素多的场景下效果显著比如对“性别”“状态码”这类字段排序时。def quick_sort(arr, lo, hi): if lo hi: return # 小区间切换插入排序 if hi - lo 16: insertion_sort(arr, lo, hi) return # 三数取中选基准 mid lo (hi - lo) // 2 pivot median_of_three(arr, lo, mid, hi) # 三路分区 lt, gt partition_three_way(arr, lo, hi, pivot) quick_sort(arr, lo, lt - 1) quick_sort(arr, gt 1, hi)注意三路分区虽然好但实现比两路复杂容易写出边界 bug。我建议先把两路写熟再上三路。写完后一定要用“全相同元素”的数组测一遍这是最容易暴露问题的地方。4. 归并排序稳定、可预测外部排序的基石4.1 归并的“稳定”到底值多少钱归并排序的核心是“分而治之再合并”。它先把数组对半切递归排好左右两半再把两个有序数组合并成一个。合并时如果左右元素相等优先取左边的这就保证了稳定性。稳定性在实际业务里非常值钱。举个我遇到的真实场景一张订单表先按金额排序再按时间排序。如果第二次排序是稳定的那么金额相同的订单会保持第一次按金额排好的顺序。如果用了不稳定的快排这个顺序就乱了得重新设计排序逻辑。所以当你需要多字段排序时归并或者任何稳定排序是首选。归并的另一个优点是复杂度非常稳定不管数据什么样都是 O(n log n)。快排最坏会退化归并没有这个问题。所以对实时性要求高、不能接受最坏情况的系统归并更让人放心。4.2 归并的空间代价与优化思路归并最大的缺点是需要 O(n) 的额外空间。合并两个有序数组时你得开一个临时数组来存放结果。对于内存敏感的场景这是个不小的负担。优化思路有几个原地归并理论上可以做到 O(1) 额外空间但实现极其复杂常数因子大实际性能往往不如普通归并。我一般不推荐。小数组切换插入排序和快排一样递归到小数组时改用插入排序减少递归开销。提前判断有序合并前先检查arr[mid] arr[mid1]如果成立说明两半已经整体有序直接跳过合并。这个优化在近乎有序的数据上效果很好。我实测过“提前判断有序”这个优化对已经有序的 10 万整数排序归并的时间从大约 40 毫秒降到了不到 5 毫秒提升非常明显。4.3 从内存归并到外部排序的延伸归并真正不可替代的地方在于外部排序。当数据大到内存装不下时你得把数据分块读进内存排好写回磁盘再做多路归并。这个过程的核心就是归并。快排做不到这一点因为它依赖随机访问整个数组。我做过一个简单的模拟把 1GB 的数据分成 100 个 10MB 的块每块读进内存用快排排好写回最后用 100 路归并合并。整个过程稳定可控内存占用始终在 10MB 左右。这就是归并在工程上的价值——它把“大问题”拆成了“能装进内存的小问题”。特性快排归并平均复杂度O(n log n)O(n log n)最坏复杂度O(n²)O(n log n)稳定性不稳定稳定额外空间O(log n) 递归栈O(n)外部排序不适合非常适合5. 堆排序与二叉堆被低估的“原地 O(n log n)”5.1 堆排序为什么“叫好不叫座”堆排序的理论指标很漂亮最坏也是 O(n log n)额外空间 O(1)原地排序。听起来完美但实际工程中用得远不如快排多。原因有两个第一堆排序的常数因子大。它的比较和交换模式是“跳跃式”的对 CPU 缓存不友好。快排是顺序扫描堆排是树状跳转缓存命中率差很多。我实测过同样 100 万随机整数堆排比快排慢大约 2 到 3 倍。第二堆排序不稳定。建堆和调整堆的过程中相等元素的相对顺序会被打乱。那堆排序还有什么用当你既需要 O(n log n) 的最坏保证又不能用额外空间时堆排是唯一选择。比如某些嵌入式场景内存极其紧张快排的递归栈都可能成为负担这时候堆排的 O(1) 空间就很有价值。5.2 建堆为什么是 O(n) 而不是 O(n log n)这是一个经典面试题。很多人以为建堆要一个个插入每次 O(log n)总共 O(n log n)。但实际上自底向上的建堆方式是 O(n) 的。原因在于大部分节点都在底层底层节点下沉的深度很小。具体算一下第 k 层的节点数约是 n/2^k每个节点下沉最多 k 层总代价是 Σ (n/2^k) * k这个级数收敛到 O(n)。所以建堆是线性的只有后续的 n 次“取堆顶再调整”才是 O(n log n)。这个结论的实际意义是如果你只需要建一个堆而不需要完整排序比如求 Top K建堆的 O(n) 成本很低非常划算。求 Top K 的标准做法就是建一个大小为 K 的堆遍历数据比堆顶大就替换最终堆里就是最大的 K 个。这个做法的时间是 O(n log K)比全排序的 O(n log n) 快得多。5.3 堆的典型应用优先队列与 Top K堆在工程里最常见的化身是优先队列。任务调度、事件驱动模拟、Dijkstra 最短路算法底层都是优先队列而优先队列的标准实现就是二叉堆。我做过一个任务调度的小系统任务有优先级需要每次取出优先级最高的。用数组每次扫描是 O(n)用堆是 O(log n)。当任务量到几万级别时差距非常明显。这个场景里堆排本身没用到但堆这个数据结构是核心。实操心得手写堆的时候最容易错的是下标计算。父节点是(i-1)/2左孩子是2*i1右孩子是2*i2。建议写完后用一组小数据手动模拟一遍下沉过程比盯着代码看有效得多。6. 非比较排序计数、桶、基数用空间换时间的三种玩法6.1 计数排序范围决定一切计数排序的思路简单粗暴如果数据是整数且范围是 0 到 k那就开一个大小为 k1 的数组统计每个值出现的次数再按顺序输出。时间复杂度 O(nk)空间 O(k)。它的命门就在这个 k。如果数据范围是 0 到 100 万但只有 100 个元素那开一个 100 万的数组就是巨大的浪费。所以计数排序只适合范围小且密集的整数数据比如年龄、分数、状态码。我踩过一个坑有一次用计数排序处理用户 IDID 范围是 0 到 10 亿结果内存直接爆了。后来改用哈希表统计加排序才解决问题。所以用计数排序前一定要先确认数据的最大值和最小值算一下 k 是否可接受。6.2 桶排序把数据分到“桶”里再各自排序桶排序是计数排序的推广。它把数据按范围分到若干个桶里每个桶内部再排序可以用插入排序或快排最后按桶顺序拼接。桶排序的性能取决于数据分布的均匀程度。如果数据均匀分布每个桶里的元素差不多整体接近 O(n)。如果数据全挤在一个桶里那就退化成桶内排序的复杂度。我实测过对均匀分布的 100 万浮点数排序桶排序比快排快大约 30%。但对正态分布的数据桶排序的优势就不明显了因为中间桶会特别大。所以桶排序适合分布已知且均匀的数据比如均匀分布的随机数。6.3 基数排序按位从低到高稳定是关键基数排序的思路是“从最低位到最高位每一位做一次稳定排序”。它通常用计数排序作为每一位的排序手段。因为每一位的范围是 0 到 9十进制计数排序的 k 很小效率很高。基数排序的关键在于每一位的排序必须是稳定的。如果某一位排序不稳定前面已经排好的低位顺序就会被破坏。这也是为什么基数排序内部用计数排序而不是快排。基数排序适合位数不多、数据量大的整数或定长字符串。比如对 100 万个手机号排序手机号是 11 位定长数字基数排序只需要 11 轮计数排序每轮 O(n)总共 O(11n)非常快。算法时间复杂度空间适用条件计数排序O(nk)O(k)整数范围小桶排序O(n) 期望O(nk)分布均匀基数排序O(d(nk))O(nk)定长整数或字符串注意这三种非比较排序都不是原地排序都需要额外空间。而且它们都不基于比较所以不受 O(n log n) 下界的约束。但代价是适用条件严格不能无脑替换快排。7. 怎么选一张决策表加几个我踩过的真实坑7.1 按数据特征选算法的决策路径学了这么多算法真正用的时候怎么选我总结了一个简单的决策路径你可以直接照着走数据量小于 50直接用插入排序。别想太多小数据下它的常数因子最小。数据近乎有序插入排序或归并带提前有序判断。快排也可以但要用三数取中。需要稳定排序归并或计数/基数如果适用。快排和堆排直接排除。数据是整数且范围小计数排序。范围大但位数少用基数排序。通用场景、内存充足快排随机或三数取中 小区间插入。这是工程默认选择。内存紧张、需要最坏保证堆排。数据大到内存装不下外部归并排序。这张路径不是绝对的但覆盖了 90% 的日常场景。我把它贴在工位上带新人的时候直接让他们照着选省了很多解释成本。7.2 我踩过的三个排序坑第一个坑以为快排永远最快。有一次处理一批几乎有序的日志数据我用了固定基准的快排结果跑了十几秒没出来。后来换成三数取中加小区间插入瞬间降到几十毫秒。这个教训让我明白快排的快是有前提的基准选择决定了它的下限。第二个坑忽略稳定性导致数据错乱。一个报表功能先按部门排序再按业绩排序。我用了快排结果同业绩的人部门顺序乱了报表看起来像是数据错乱。后来换成归并问题消失。多字段排序时稳定性不是可选项是必选项。第三个坑计数排序的范围没检查。前面提过用计数排序处理大范围 ID内存直接爆了。用非比较排序前先算 k 的大小这是铁律。7.3 面试里排序算法怎么答才不露怯面试问排序通常不是让你背代码而是看你能不能说清楚取舍。我的答题框架是这样的先说分类基于比较的和非比较的基于比较的有 O(n log n) 下界。再说三个 O(n log n) 的取舍快排平均最快但不稳定、最坏会退化归并稳定但费空间堆排原地但常数大。然后说优化快排的三数取中、小区间插入、三路分区归并的提前有序判断。最后说场景小数据用插入稳定用归并通用用快排内存紧用堆排整数范围小用计数。这个框架答下来基本能覆盖面试官想听的所有点。我当年就是靠这个框架拿下了好几个 offer后来带人也一直用这套。排序算法这东西学一遍只能记住概念真正理解得靠动手写、动手测、动手踩坑。我建议你把每个算法都手写一遍然后用同一组数据跑一遍对比时间和内存。这个过程比看十篇文章都管用。等你亲手把快排写退化一次把归并的稳定性验证一次把计数排序的内存撑爆一次这些知识才真正变成你自己的。