1. 从一道题聊起为什么我专门为 sort 做了一篇学习笔记大概几个月前我在准备一次技术面试复盘的时候发现了一个让我有点尴尬的事情。让我手写一个冒泡排序我能写出来让我说说快排的思想我也能聊几句。但一旦把问题换成一个具体的场景比如“给你一百万个订单记录按金额从高到低排序金额相同的按时间从旧到新排你选什么算法为什么”——我就开始卡壳了。不是不知道答案而是我发现自己对排序算法的理解其实一直停留在“背代码”的层面没有真正建立起一套完整的判断体系什么场景下该选什么排序稳定性到底影响什么工程里的 sort 函数底层又做了什么取舍。于是我就花了一段时间把排序算法从头到尾系统地捋了一遍写了这篇学习笔记。这篇笔记不是简单地把各种排序算法的代码贴一遍而是把我整理过程中的思路、对比、踩坑和实际应用场景都记录下来。如果你也准备系统地过一遍排序算法或者刷题时经常被排序相关的变形题难住又或者工作中经常需要处理数据排序但不确定底层机制这篇笔记应该能帮你省下不少时间。这篇笔记的核心内容分几条线一是常见排序算法的原理和代码实现二是各种算法之间的横向对比和选型逻辑三是 C / Java 等主流语言里 sort 函数的源码级行为分析四是排序在刷题和实际业务里的经典应用场景。我会刻意避开那些“面试八股文”式的罗列尽量用踩过坑的人的口吻来讲。2. 先搞清楚排序算法到底在解决什么问题怎么评判一个排序好不好2.1 排序在真实世界里无处不在的三种形态排序说起来很简单就是把一组元素按某种规则排成有序序列。但放到真实项目里排序通常不是孤立存在的它有三种常见形态。第一种是最直接的“显式排序”用户点了一下“按价格排序”后端对商品列表做一次排序然后返回。这种场景下数据量可能是几千条到几百万条需要排序的字段可能是一个或多个还要考虑分页、稳定性、内存占用等问题。第二种是“隐式排序”很多算法和数据结构的底层都依赖有序性。比如二分查找的前提是有序数组数据库索引的构建依赖排序最大堆和最小堆本质上就是一种部分有序结构。你写贪心算法时经常需要先排序才能做出局部最优决策你写合并区间之类的题目时排序是第一步。在这些场景里排序不是目的而是手段但它往往是算法能否高效运行的关键前提。第三种是“排序作为业务规则的一部分”比如排行榜、热门推荐、任务调度优先级、阳光分班这类带有分配性质的场景。这类排序往往有复杂的比较规则不是简单地比一个数字大小而是多个字段的复合比较。这时候你怎么设计比较器、怎么保证排序的确定性和稳定性会直接影响业务结果的正确性。可以说排序是算法和数据结构里最基础、应用面最广的模块。搞懂了排序你对时间复杂度、空间复杂度、稳定性、分治思想、堆结构这些概念的理解会一下子通透很多。2.2 评判排序的三个核心维度我在整理笔记时发现所有的排序算法都可以从三个维度去横向对比这也是面试和工程选型时最核心的三个维度。第一个维度是时间复杂度。这个大家都熟悉但我觉得值得强调的是“最好、平均、最坏”三种情况要分开看。比如快排平均是 O(nlogn)但你如果每次选的基准值都很糟糕它会退化到 O(n²)。而堆排序无论输入是什么都能稳定在 O(nlogn)这就是它的优势。第二个维度是空间复杂度。有些排序是完全原地进行的额外空间是 O(1)比如堆排序、插入排序有些排序需要额外的数组空间比如归并排序需要 O(n) 的辅助空间这也是它在极度追求内存的场景下不太讨喜的原因。第三个维度是稳定性。这里的“稳定”指的是如果两个元素的值相等排序后它们的相对顺序会不会改变。会改变的叫不稳定排序不会改变的叫稳定排序。稳定性有什么实际意义最典型的例子是多重排序。假设你先按时间排序再按金额排序如果第二次排序是不稳定的那么金额相等的记录内部时间顺序就可能乱掉。换句话说稳定排序让你可以“叠加”排序条件而不稳定排序会让你丢失上一轮的排序结果。理解了这三个维度你再看各种排序算法时看到的就不是一堆孤立的代码而是一张有规律的决策地图。2.3 为什么不存在一个“包打天下”的排序算法这个问题是我整理笔记时最早想问自己的既然归并排序又稳定又快为什么不全用归并既然快排平均最快为什么不全用快排答案是每个算法都有代价。快排虽然平均快但最坏情况不稳定而且它是“递归”的实现不好可能会有栈溢出的问题归并排序稳定、时间复杂度确定但需要额外内存而且在处理小规模数据时递归调用的开销反而比插入排序还大。堆排序空间最优但它的实际运行速度通常比快排慢因为它的缓存局部性比较差数组访问的模式不够线性。所以工程里的做法往往是混合式的数据规模大的时候用 O(nlogn) 的算法数据规模小到一定程度就直接用插入排序因为常数因子小实际更快。这也是后面讲 C 和 Java 的 sort 实现时你会看到的现象真实世界里的 sort 从来不是单一算法而是几种算法的组合。3. O(n²) 那批基础排序算法为什么说它们简单但“不简单”3.1 冒泡排序最容易理解但工程里最不推荐冒泡排序的思路是每一轮从头到尾比较相邻元素如果顺序不对就交换这样每一轮结束当前未排序部分的最大值就会像气泡一样“冒”到末尾。冒泡排序的时间复杂度是 O(n²)最好情况数组已经有序下如果加了标志位优化可以是 O(n)但平均和最坏情况下还是 O(n²)。空间复杂度是 O(1)且它是稳定排序。那为什么说工程里最不推荐因为冒泡排序的交换操作实在太频繁了每次比较后可能都要交换这种内存写入的代价比其他内层循环更重的算法要高。虽然理论上复杂度和其他 O(n²) 算法一样但常数因子偏大实际执行时间通常是最差的。不过冒泡排序在教学上有它的价值你理解它之后对“交换”和“迭代”这两个基础操作会有直观的概念写起来也几乎不可能写错。我自己的体会是冒泡排序适合作为“理解排序是什么”的启蒙算法但你不会想在生产环境里真正调用它。void bubble_sort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; // 没有发生交换说明已经有序 } }这个优化版加了swapped标志位一旦一轮下来没有发生任何交换说明数组已经有序可以提前退出。这算是最常见的冒泡排序优化手段。3.2 选择排序交换次数少但是不稳定选择排序的思路更直接每次从未排序部分选出最小值放到已排序部分的末尾。它做交换的次数是 O(n)每次交换最多把一个元素放到最终位置所以交换操作比冒泡少很多。但它的比较次数依然是 O(n²)不管输入是否已经有序。选择和冒泡最大的区别在于稳定性。选择排序是不稳定的这一点很多人会忽略。比如数组[5, 8, 5, 2]第一轮选出最小值 2和第一个 5 交换这样两个 5 的相对顺序就变了原来在前面的 5 跑到了后面。这种不稳定性在单纯对数字排序时看不出来但如果元素是对象按某个 key 排序稳定性就可能影响后续处理。我自己在刷题的时候很少写选择排序但它的一个变体思路很常用不完整排序只求第 K 小或前 K 小的元素那就是快速选择的思想。从这个角度看选择排序虽然本身不实用但它引出了“选择”这一类问题的思路。3.3 插入排序小数组里的隐形冠军插入排序的思路有点像打扑克时整理手牌从第二个元素开始每次把当前元素插入到前面已经有序的序列中的正确位置。它最好的情况是 O(n)数组已经几乎有序最坏和平均是 O(n²)额外空间 O(1)并且是稳定排序。插入排序的亮点在于它的常数因子非常小。当数据规模小通常是几十个以内或者数组基本有序时插入排序的实际运行速度往往比归并排序、快排还要快因为后者的递归开销和大范围内跳转的缓存不友好性会拖慢速度。所以你会看到很多工业级的排序实现包括 C 的std::sort和 Java 的Arrays.sort在递归到一定深度时都会切换到插入排序来收尾。这里有个实操建议如果你自己实现快排或归并递归到子数组长度小于某个阈值我自己常用 16 或者 32时直接用插入排序。这一行优化有时候能让整体性能提升 5% 到 10%。插入排序还有一个二分优化的版本使用二分查找来定位插入位置能把比较次数降到 O(nlogn)但插入过程本身的移动次数依然是 O(n²)所以时间复杂度没有质的改变。这个优化在面试时偶尔会被问到知道即可。void insertion_sort(vectorint arr) { int n arr.size(); for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } }3.4 三种 O(n²) 排序对比各自适合什么场景算法最好时间平均时间最坏时间空间稳定性特点冒泡排序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(nlogn) 那批算法出场了。4. O(nlogn) 进阶算法工程世界的绝对主力4.1 归并排序稳定且有确定性归并排序是我个人非常喜欢的一个算法它几乎是“分治法”思想最清晰的教学样本。思路很简单把数组从中间分成两半分别排序再合并两个有序数组。递归到只剩下一个元素时天然有序。归并排序最好、最坏、平均时间复杂度都是 O(nlogn)稳定但需要 O(n) 的额外空间。它最大的优点是“确定性”不管输入是什么性能都不会退化。相比之下快排最坏会退化成 O(n²)归并没有这个问题。实现归并排序时有一个细节很关键合并时如果左半部分的当前元素和右半部分的当前元素相等要先把左半部分的元素放进结果数组。这样才能保证稳定性。void merge_sort(vectorint arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); }这里mid left (right - left) / 2是防止(left right)溢出的一种写法在 Java 和 C 里都是一个好习惯。很多新手容易写成(left right) / 2在极端大数组时可能出问题。归并排序还有一个优势是适合外部排序数据量太大内存放不下需要借助磁盘和多路归并。这也是为什么数据库和分布式计算框架里经常能看到它的影子。4.2 快速排序名字里的“快”不是白叫的快排的核心思想是选一个基准值pivot把数组分成小于基准值和大于基准值的两部分然后递归处理这两部分。它平均是 O(nlogn)但最坏情况会退化到 O(n²)空间复杂度是 O(logn)递归栈而且是不稳定排序。快排最需要重点研究的就是基准值的选择。如果每次基准值都恰好是数组的最小值或最大值那分区就会极度不平衡递归深度变成 O(n)时间复杂度退化为 O(n²)。常见的解决方法有三个一是随机选基准值二是三数取中从 left、mid、right 三个位置取中位数作为基准值三是在递归深度超过一定阈值时切换到堆排序这就是 introsort 的思路。在刷题时我经常用快排的“分区思想”而不是完整排序。最典型的是求“第 K 大”的问题每次分区后根据基准值的位置和 K 的关系只需要递归处理一侧平均时间复杂度是 O(n)比完整排序后再取第 K 个要快。这也是快排在算法思维上的一个延伸。int partition(vectorint arr, int left, int right) { int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr[i], arr[j]); i; } } swap(arr[i], arr[right]); return i; }上面这个 Lomuto 分区法写起来最简单但它有一个问题当数组中有大量重复元素时分区可能很不平衡。工程上更常用的是 Hoare 分区法左右指针同时向中间移动。我建议你把这两种分区都写一遍体会一下它们的区别。这个经历对理解快排非常有帮助。4.3 堆排序不靠递归只靠一个堆堆排序的思路又不一样先把数组构建成一个最大堆然后每次把堆顶的最大元素和堆尾交换堆的大小减一再调整堆重复这个过程就得到了升序结果。它的时间复杂度稳定在 O(nlogn)空间 O(1)但不稳定。堆排序最典型的优点是“原地排序 时间复杂度确定”所以在嵌入式系统或者内存极度受限的场景里它很有存在感。缺点前面说过由于它访问数组的方式跳跃性太强父节点和子节点的下标是2*i和2*i1的关系缓存不友好实际运行速度通常比快排慢。堆排序还经常用在“大数据量下取前 K 个最大/最小”的问题上。维护一个大小为 K 的小根堆遍历数据时如果当前元素比堆顶大就替换堆顶并调整堆。这样一遍扫描就能得到最大的 K 个元素时间复杂度是 O(nlogK)在 K 远小于 n 时非常高效而且不需要把整个数据加载进内存。我自己在实现堆排序时踩过一个挺常见的坑调整堆的操作要写成“下沉”而不是“上浮”。建堆时要从最后一个非叶子节点往前调整也就是n/2 - 1到 0。如果搞反了方向或写错了节点顺序排序结果就会错。4.4 三种 O(nlogn) 排序怎么选我的判断逻辑算法最好/平均/最坏空间稳定性实际速度主要局限归并排序O(nlogn) / O(nlogn) / O(nlogn)O(n)稳定较快需要额外内存快速排序O(nlogn) / O(nlogn) / O(n²)O(logn)不稳定最快最坏退化需优化堆排序O(nlogn) / O(nlogn) / O(nlogn)O(1)不稳定中等缓存不友好在实际工程中我的选择逻辑大概是这样如果对稳定性有要求优先归并如果内存比较紧张优先堆排序如果数据量适中、内存足够、且不要求稳定性直接快排。如果数组本身很小十几二十个元素直接用插入排序更省事。这套选择逻辑可以说覆盖了绝大多数日常写代码的场景。5. 线性时间的排序“外挂”计数、桶、基数排序5.1 什么时候排序能突破 O(nlogn) 的下限很多人第一次听到“比较排序的下限是 O(nlogn)”时会误以为排序只能这么快。这个结论有个前提基于比较的排序。如果数据本身有结构比如是一组范围有限的整数或者可以拆成多个位来分别处理那我们就可以跳出比较排序的框架用空间换时间。最典型的例子是计数排序。它的做法是先统计每个值出现的次数然后根据计数把元素放回原数组。计数排序的时间复杂度是 O(nk)其中 k 是数据的取值范围。如果 k 不是很大比如待排序数字都在 1 到 1000 之间它会比任何比较排序都快。但它有两个硬伤一是要求数据是非负整数二是如果 k 特别大比如排序几个从 1 到 10⁹ 的数字额外空间会直接爆炸。我在刷题时如果题目里明确说“数组中的元素范围在 0 到 100 之间”我第一反应就会想到计数排序。它代码不长效率极高在特定场景里就是“降维打击”。5.2 桶排序和基数排序把数据“分桶”后再处理桶排序的思路是把数据按范围分到若干个桶里对每个桶分别排序再合并。它的平均复杂度是 O(nk)但最坏情况下所有数据都进同一个桶会退化为桶内所用的排序算法。桶排序对数据分布有要求数据要尽可能均匀分布。如果数据集中在某个区间桶就没意义了。基数排序则是另一种思路把整数按位拆开从最低位开始逐位执行稳定排序通常用计数排序。对 d 位数字时间复杂度是 O(d(nr))其中 r 是基数。它不直接比较元素大小而是逐位处理。基数排序在排序定长数字或字符串时很好用但要求数据能拆成独立的位。这三类线性排序在刷题里出现的频率不像快排、归并那么高但它们体现了“利用数据特性”的思维。我自己的感受是如果你能把计数排序彻底搞懂你再看很多需要“统计频次”的题目思路会开阔很多。6. 工程里的 sort 函数到底是怎么实现的6.1 C 的 std::sort不是快排的“简单的快排”C 的std::sort是很多 C 开发者的老朋友但它的底层实现其实是个混合算法。在绝大多数标准库实现里std::sort采用的是introsort内省排序先用快排进行递归当递归深度超过某个阈值时切换到堆排序保证最坏情况下依然是 O(nlogn)而当递归到子数组规模足够小通常是 16 或类似阈值时切换到插入排序来收尾。这套组合拳让std::sort在平均情况下拥有快排的高速在最坏情况下有堆排序的兜底小规模数据有插入排序的低常数因子综合性能非常能打。但使用std::sort时有几个注意点。第一它不是稳定排序如果你需要稳定性用std::stable_sort第二std::sort要求迭代器是随机访问迭代器因此它对vector、array这类容器适用但对list不能用第三排序整个数组时如果写成sort(arr, arr n)或者sort(arr.begin(), arr.end())排序区间是左闭右开的这一点新手特别容易搞错。6.2 Java 的 Arrays.sort基本类型和对象走的是两条路Java 的Arrays.sort很有意思它对基本类型数组和对象数组采用了不同的策略。对基本类型数组比如int[]Java 使用的是Dual-Pivot Quicksort双轴快排。双轴快排选取两个基准值把数组分成三个区间比经典快排的单基准分区在大多数情况下效率更高。对对象数组比如Integer[]或自定义对象Java 使用的是TimSort。TimSort 是一种结合了归并排序和插入排序的算法它首先扫描数组找出自然有序的“run”片段再用归并的方式把这些片段合并起来。TimSort 的优势在于它非常善于利用输入数据的已有有序性如果数组本身已经近乎有序TimSort 的效率可以接近 O(n)。这就出现了一个有意思的差异基本类型的排序是不稳定的双轴快排不稳定而对象数组的排序是稳定的TimSort 是稳定的。如果你写过 Java并且关心过排序稳定性这个差异特别值得记住。6.3 自定义比较器排序结构体C、Java、Python 的写法对比在实际业务中我们很少直接排一个整数数组更多是排结构体或对象。这是一个非常高频的场景值得单独拿出来对比。C 里最常见的做法是通过std::sort传入自定义比较函数或 lambda处理结构体数组。比如排序学生先按分数降序分数相同按姓名升序struct Student { string name; int score; }; vectorStudent students {{Alice, 90}, {Bob, 85}, {Eve, 90}}; sort(students.begin(), students.end(), [](const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; // 分数从高到低 return a.name b.name; // 姓名从低到高 });Java 里可以用Comparator或Comparable实现同样逻辑Arrays.sort(students, (a, b) - { if (a.score ! b.score) return Integer.compare(b.score, a.score); return a.name.compareTo(b.name); });Python 里最干净的写法是用key参数利用元组按位比较的特性students.sort(keylambda s: (-s[score], s[name]))Python 这种key写法有个优点它不会改变元素的原始键值也不容易在比较器逻辑上出错。反观 C 和 Java 的比较器有一个非常隐蔽的坑必须满足“严格弱序”。也就是说如果 a 和 b 相等比较器对(a, b)返回 false对(b, a)也必须返回 false。如果写反了导致两个相等元素互相“小于”对方排序结果可能是未定义行为甚至直接崩溃。这个问题在数据量大的时候才会暴露排查起来非常痛苦。6.4 稳定排序和 sort 的幂等性踩过的真实案例我在工作中踩过一个和稳定性直接相关的坑。当时有个订单列表我需要先按订单优先级排序再按创建时间排序。我第一版写得想当然了直接对列表做了一次“按创建时间”排序再做了一次“按优先级”排序结果发现两次排序后同一优先级的订单内部时间顺序完全乱了。后来查了文档才发现我用的排序算法是不稳定的第二轮排序把第一轮的结果破坏了。解决方案很简单要么在比较器里同时比较两个字段优先级优先时间次之要么把排序算法换成稳定的归并排序。我自己后来养成了一个习惯只要排序字段多于一个我就直接在比较器里把所有字段都写上而不是分多次排序。这样逻辑清晰也完全绕开了稳定性问题。这个经验完全适用于刷题场景。你写合并区间、求重叠长度之类的题目时通常会对 start 排序这时候如果你还要对 end 做二次排序千万不要分两次 sort一道比较器里把规则写全比什么都稳妥。7. 排序在刷题和算法题里的经典应用套路7.1 排序 双指针区间题和两数之和类问题排序最常见的刷题套路是和双指针配合。最经典的是两数之和问题给定一个数组和一个目标值找两个数等于目标值。如果不排序最简单的做法是 O(n²) 暴力加上排序后用左右双指针从两端往中间移动时间复杂度降到 O(nlogn)排序的代价 O(n)扫描的代价。同样的套路还可以扩展到三数之和、四数之和、最接近的三数之和等一系列问题。合并区间类题目也是排序 扫描的典型。做法是先把区间按左端点排序然后遍历区间维护当前合并的左右端点。如果下一个区间的左端点小于等于当前右端点就扩展右端点否则把当前区间加入结果并更新为新区间。这类题目难的不是排序本身而是你能否想到“先排序可以简化问题”这一步。7.2 排序 贪心从“先做哪个”到“最优解”贪心算法里排序几乎是一种必备前置操作。我印象最深的是“会议室安排”问题给出一系列会议的开始和结束时间问最多能参加多少场会议。解法是先按结束时间排序然后贪心地选择结束时间最早且与当前时间不冲突的会议。如果去掉排序这个问题很难找到高效的解法一排序思路立刻变得清晰。另一个例子是“分发饼干”问题每个孩子有一个饥饿度每块饼干有一个大小问最多能满足多少个孩子。先对孩子和饼干都排序然后双指针贪心匹配也是一个很自然的做法。这类题目做多了以后你会形成一个条件反射遇到最优化问题先思考排序能不能让决策顺序变得简单。7.3 排序 自定义比较器解决“拼接最大数”之类的玄学题有些题目的比较器设计非常反直觉最典型的是“给定一组非负整数重新排列它们的顺序使之组成一个最大的数”。比如[3, 30, 34, 5, 9]正确的排序结果是9534330而不是把数字从小到大排。这个题的核心不在于排序算法本身而在于比较规则如果a b b a字符串拼接那么 a 应该排在 b 前面。当你把这套自定义比较器传给 sort 函数以后剩下的工作就全交给排序算法了。这个例子很好地说明了一件事sort 函数是通用的骨架真正的业务逻辑全在比较器里。能不能写出正确的比较器往往决定了这类题目你能不能 AC。7.4 用排序优化“区间重叠”与“前缀交集”问题还有一类题目像“计算所有区间重叠总长度”或“合并所有人可用的空闲时间段”本质上是先排序然后线性扫描维护状态。排序本身 O(nlogn)扫描 O(n)整体效率很不错。我在刷题时发现这类题最坑的地方在边界条件区间开头和结尾的闭开区间、重叠但不包含的情况、正好首尾相接的情况。如果你能先把这些边界情况在纸上画清楚再开始写代码会比一边写一边找 bug 快得多。我自己的经验是合并区间类题目的判断条件统一用“下一个区间的左端点 当前合并区间的右端点”作为重叠判据并在扫描时同时更新右端点的最大值而不是简单累加就不会出错。8. 实践中的常见问题与避坑记录8.1 快排最坏情况真的会发生吗怎么避免很多人觉得快排最坏情况是理论上的实际不会碰到。但如果你每次都用第一个元素或最后一个元素作为基准值而输入恰恰是近乎有序的数组那最坏情况就会真实发生递归深度接近 n性能会差到让你怀疑人生。我自己的规避方法是在小规模数组上直接用三数取中选基准在更大规模的数据上用随机化选基准。两条路都比固定取一端好得多。而如果你是在实现工业代码直接上 introsort 思路就好设置一个最大递归深度超过这个深度就切到堆排序。8.2 比较器不满足严格弱序会出什么问题前面提过C 的std::sort比较器必须满足严格弱序。这里的“严格弱序”可以简单理解为对于任意元素 xcomp(x, x)必须为 false如果comp(a, b)为 true那么comp(b, a)必须为 false传递性不能出问题。如果违反第一条比如你手滑把a b写成了a b在a和b相等时comp(a, b)和comp(b, a)都会返回 true。这会导致排序算法内部的状态错乱轻则结果错误重则触发未定义行为。这类 bug 通常极难排查因为它不会稳定复现只会在数据量变大时偶尔闪一下。我建议你写完比较器以后专门想一下“如果两个元素的 sort key 相等我的比较器返回什么”这个问题能帮你避免一大半比较器 bug。8.3 O(nlogn) 一定比 O(n²) 快吗别忘了常数因子这是一个很反直觉但很现实的问题。O(nlogn) 和 O(n²) 描述的是增长率不是说任何输入规模下前者一定更快。当 n 非常小比如 n 5 或者 n 10插入排序的常数因子优势会盖过归并排序和快排递归调用的开销。这就是为什么工业级排序实现会在递归到小规模子数组时切换到插入排序。我在实际测试中写过一个小实验对 20 个元素的随机数组分别用插入排序和快排排序插入排序的耗时明显更短。如果对 10 万个元素排序快排就远远领先了。这个结论时刻提醒我不要只背复杂度也要理解常数项的意义。8.4 常见排序问题速查表面试和自查都能用问题答案数组基本有序用什么排序最快插入排序O(n)或者 TimSort 系的排序数据量大内存紧张要求最坏 O(nlogn)堆排序要求稳定并且有额外内存归并排序数据范围小且是非负整数计数排序O(nk)求第 K 大元素快速选择基于快排分区平均 O(n)面试手写排序选哪个快排或归并取决于是否要求稳定刷题时 sort 对象数组直接使用语言内置 sort 自定义比较器不要手写排序这张表几乎是我每次写排序相关代码时脑子里都会过一遍的决策清单。9. 我个人整理排序笔记时的一些心得写这篇笔记的过程其实比我预期的收获要大。最开始我只是想系统过一遍排序算法结果整理下来发现排序这个主题几乎串联起了算法学习的一大半核心概念分治、递归、堆、稳定性、复杂度分析、工程实现、比较器设计。可以说把排序真正吃透你再去学其他算法时很多底层思维都是相通的。最后分享一个我最近养成的习惯每次需要用排序时不直接写sort完事而是先花几秒钟想三件事——这个排序是否需要稳定数据规模大概多大内存是否敏感比较器有没有把所有需要比较的字段都包含进去这三步想清楚排序相关的大部分问题基本都能提前规避掉。排序算法其实也是这样看起来简单背后的门道多得很值得反复琢磨。