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(vector<int>& 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(vector<int>& 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(vector<int>& 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(vector<int>& 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*i+1的关系），缓存不友好，实际运行速度通常比快排慢。
堆排序还经常用在“大数据量下取前 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(n+k)，其中 k 是数据的取值范围。如果 k 不是很大（比如待排序数字都在 1 到 1000 之间），它会比任何比较排序都快。但它有两个硬伤：一是要求数据是非负整数，二是如果 k 特别大（比如排序几个从 1 到 10⁹ 的数字），额外空间会直接爆炸。
我在刷题时，如果题目里明确说“数组中的元素范围在 0 到 100 之间”，我第一反应就会想到计数排序。它代码不长，效率极高，在特定场景里就是“降维打击”。
5.2 桶排序和基数排序：把数据“分桶”后再处理
桶排序的思路是把数据按范围分到若干个桶里，对每个桶分别排序，再合并。它的平均复杂度是 O(n+k)，但最坏情况下（所有数据都进同一个桶）会退化为桶内所用的排序算法。桶排序对数据分布有要求：数据要尽可能均匀分布。如果数据集中在某个区间，桶就没意义了。
基数排序则是另一种思路：把整数按位拆开，从最低位开始，逐位执行稳定排序（通常用计数排序）。对 d 位数字，时间复杂度是 O(d(n+r))，其中 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; }; vector<Student> 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(key=lambda 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比较器必须满足严格弱序。这里的“严格弱序”可以简单理解为：
- 对于任意元素 x，
comp(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(n+k)） |
| 求第 K 大元素 | 快速选择（基于快排分区），平均 O(n) |
| 面试手写排序，选哪个 | 快排或归并，取决于是否要求稳定 |
| 刷题时 sort 对象数组 | 直接使用语言内置 sort + 自定义比较器，不要手写排序 |
这张表几乎是我每次写排序相关代码时脑子里都会过一遍的决策清单。
9. 我个人整理排序笔记时的一些心得
写这篇笔记的过程，其实比我预期的收获要大。最开始我只是想系统过一遍排序算法，结果整理下来发现，排序这个主题几乎串联起了算法学习的一大半核心概念：分治、递归、堆、稳定性、复杂度分析、工程实现、比较器设计。可以说，把排序真正吃透，你再去学其他算法时，很多底层思维都是相通的。
最后分享一个我最近养成的习惯：每次需要用排序时，不直接写sort完事，而是先花几秒钟想三件事——这个排序是否需要稳定？数据规模大概多大，内存是否敏感？比较器有没有把所有需要比较的字段都包含进去？这三步想清楚，排序相关的大部分问题基本都能提前规避掉。排序算法其实也是这样，看起来简单，背后的门道多得很，值得反复琢磨。
