1. 排序与排列竞赛选手绕不开的核心基本功我接触算法竞赛这么多年最深的一个体会就是排序不是“会写”就行而是要在任何场景下都“信手拈来”。无论你是刚接触蓝桥杯、ICPC、Codeforces还是在应付各类机试和笔试排序和排列几乎是无处不在的——它可能是题目本身更多的是作为其他算法的前置步骤。很多看起来跟排序八竿子打不着的题最后都会归约到“先把数据排个序”这个动作上。所以竞赛圈里一直有句老话排序和排列是算法选手的“肌肉记忆”。这篇文章不打算把《算法导论》里所有的证明搬过来粘贴一遍而是从实际比赛和刷题的角度把排序、排列里面真正有价值、能帮你拿分的东西讲透。我会着重讲几个方面各种排序算法的原理和适用场景、竞赛中真正依赖的库函数用法、手写排序的模板以及背后的复杂度分析、排列的生成思路还有一组很容易被忽略但比赛中很常见的问题——拓扑排序。你会发现这些东西一旦串联起来它们彼此之间的关联非常紧密理解了这层关系很多题目在你眼里就会变得透明很多。2. 排序算法全景先搞清楚每种“武器”的脾气2.1 比较排序的家族谱系与复杂度下界排序算法大致可以分为两类基于比较的排序和不基于比较的排序。前者包括我们熟悉的冒泡、选择、插入、希尔、归并、快排、堆排后者主要是计数排序、基数排序和桶排序这几位“另类选手”。基于比较的排序有一个极其重要的理论结论在最坏情况下任何基于两两比较的排序算法时间复杂度都不可能低于 O(n log n)。这个结论的证明用的是决策树模型——n 个元素的排列有 n! 种可能而一次比较最多产生两个分支所以树的高度至少是 log(n!)由斯特林公式可知 n! 约等于 (n/e)^n取对数以后就是 O(n log n)。这个结论的意义在于当你看到一道题要求排序并且数据范围是 10^6 级别的你就不用费心思想什么神奇的比较排序能突破 O(n log n)——不存在这种可能老老实实选快排或者归并就好。但这并不意味着所有比较排序都“一样快”它们之间的常数因子差异很大。冒泡排序和选择排序是 O(n^2)一般在数据量超过 5000 的时候就已经能感觉到明显的延迟。插入排序虽然理论复杂度也是 O(n^2)但它在近乎有序的数据上表现极好可以跑到 O(n)所以很多工业级排序实现会把插入排序作为小规模数据的收尾手段。希尔排序则是插入排序的改进版通过增量分组让元素先“大致有序”再逐步细排它的复杂度分析在竞赛中基本不会涉及但在《算法导论》的习题里偶尔会出现。2.2 快排、归并、堆排竞赛中的“三大件”快速排序是竞赛中最常用的排序算法没有之一。它的核心思想是分治选一个基准元素pivot把小于它的放左边大于它的放右边然后递归处理左右两侧。平均时间复杂度 O(n log n)但最坏会退化成 O(n^2)原因在于如果每次选的 pivot 恰好是最大或最小元素分割就严重失衡了。标准库里的 sort 函数做了一件很重要的事它会在递归深度过深时切换为堆排序保证最坏情况下仍然是 O(n log n)。这就是“内省排序”策略也是为什么竞赛中我们很少手写快排——std::sort 已经帮你把坑填平了。归并排序的思路同样是分治但它是先递归到底再在回溯过程中合并两个有序序列。合并过程需要 O(n) 的额外空间这是它不如快排常用的主要原因。但归并排序有两个无可替代的优点稳定、适合外部排序。所谓稳定就是相等元素的相对顺序不会被破坏。有的题明确要求“当关键值相同时按输入顺序输出”这时候稳定排序就是唯一选择。另外归并排序是分治思想的绝佳载体很多涉及“逆序对”的题目标准解法就是在归并排序的合并阶段顺手计数。堆排序则有些特殊它利用完全二叉树的性质在 O(n log n) 时间内完成排序且不需要额外空间。不过因为它的常数较大实际比赛中很少直接用堆排序来给数组排序。堆真正发光发热的地方是“动态维护最值”——比如优先队列。所以我会把它归入“数据结构工具”而非“常用排序手段”。但你需要清楚它的实现原理因为“手写堆”在竞赛中仍然是可能出现的考点。2.3 线性排序的适用边界计数、基数、桶计数排序的思路非常暴力既然比较排序有 O(n log n) 的天花板那我干脆不比了直接用值域开数组统计每个值出现的次数然后按顺序输出。这样做的时间复杂度是 O(n k)其中 k 是值域范围。只要 k 的范围可控比如 10^6 以内这就是一个快到离谱的排序方式。但它有两个致命限制只能排整数如果值域太大比如 10^9开数组就不可行了需要配合离散化使用。基数排序则是计数排序的推广它把数字拆成若干“位”从低位到高位逐位进行稳定计数排序。复杂度是 O(d * n)d 是位数。适用于大整数、字符串按字典序等场景。桶排序则是把数据按区间分到若干个桶里每个桶内再单独排序最后合并。它适合数据分布比较均匀的浮点数排序。这里我有一个很实用的经验竞赛中真正用到线性排序的场景其实不多因为数据范围一般都受到限制。但理解它们的原理对解决“排序问题变种”极有帮助——比如你需要统计频率、需要按某种权重排序这些本质上都是“映射 排序”的组合。3. 赛场上的 sort 实战从入门到不翻车3.1 std::sort 的正确姿势与比较器写法在 C 竞赛编程里std::sort 是默认武器。它基于内省排序实现足够快足够稳。但我见过太多选手在比较器上翻车导致卒于排序。最典型的错误是比较器没有满足“严格弱序”条件结果程序直接崩溃或者返回随机结果。严格弱序strict weak ordering听起来很学术其实就三条规则反对称性a b 和 b a 不能同时成立、传递性a b 且 b c 则 a c、不可比等价性a 不小于 b、b 也不小于 a 时认为两者等价。一个经典的坑是“比较器中使用大于等于号”。你可能会想当然地写 return a b这在数学上看好像没问题但实际上它违反了反对称性——a b 和 b a 在 a 等于 b 时可以同时成立这意味着严格弱序被破坏。正确写法是 return a b或者更规范地用 lambda 让 sort 按你想要的顺序排列。再看一个常见需求结构体多关键字排序。比如有 n 个人要按年龄升序、年龄相同按姓名升序。新手喜欢写一堆嵌套的 if-else其实用 C 的 tie 可以一行解决。#include bits/stdc.h using namespace std; struct Person { int age; string name; }; int main() { vectorPerson persons {{23, Alice}, {20, Bob}, {23, Charlie}}; sort(persons.begin(), persons.end(), [](const Person a, const Person b) { if (a.age ! b.age) return a.age b.age; return a.name b.name; }); // 更优雅的写法 sort(persons.begin(), persons.end(), [](const Person a, const Person b) { return tie(a.age, a.name) tie(b.age, b.name); }); for (auto p : persons) cout p.age p.name \n; return 0; }tie 的比较规则就是“按成员顺序依次比较”第一个不同的成员决定结果。这比手写嵌套判断简洁太多而且不容易漏条件。3.2 结构体排序时 operator 重载的取舍结构体排序还可以通过重载小于运算符实现这样 sort 不需要额外传比较器代码看起来更整洁。这种方式适合那些“排序规则在数据结构定义里就确定好”的场景。struct Person { int age; string name; bool operator(const Person other) const { return tie(age, name) tie(other.age, other.name); } };需要注意的一点是如果重载了 operator那么“小于”的语义应当和题目要求的排序方向一致。如果你需要按年龄降序排却把 operator 重载成了升序那你还是得另写比较器或者用反向迭代器。我的建议是能用 lambda 的地方就用 lambda因为排序方向在调用处才最清楚写在结构体里反而限制了灵活性。只有当结构体被多个容器、多个算法复用排序规则完全统一时才值得重载 operator。还有一个很隐蔽的坑如果你用的是 C20 的“宇宙飞船运算符”语法上很方便但请务必确认比较顺序符合预期。总之不要为了炫技而牺牲可读性比赛中最重要的是代码正确且快速写完。3.3 字符串排序细节字典序与自然排序的陷阱字符串排序在竞赛中也极其常见。默认的字符串比较是基于字典序的即逐字符比较 ASCII 码。但这里有个容易踩坑的真实问题字符串“10”和“9”按字典序比较“10”会排在“9”前面因为字符 1 的 ASCII 码小于 9。如果题目要求按“数值”排序你必须先把字符串转成整数或者自定义比较器按长度、按数值位来比较。另外字符串排序还经常涉及“自定义排序规则”比如按字母频率、按字符串长度、按特殊字符优先级。这时候比较器里就不仅仅是直接比较字符串本身而是预处理出映射表后再比较。举个例子有一道很经典的字符串排序题给定一组单词要求按它们中“某个字符出现次数”的降序排列次数相同按字典序升序。这类题比较器的编写要特别小心尽可能把预处理结果存下来避免在比较器里重复计算导致超时。3.4 其他语言中的排序要点JS、Java、Python虽然 C 是竞赛主流但我发现很多读者在自学阶段用的是 JavaScript 或 Python。JS 的数组排序方法 sort 有一个大坑默认按字符串字典序排序所以 [10, 9, 100].sort() 的结果是 [10, 100, 9]而不是 [9, 10, 100]。必须显式传入比较函数 arr.sort((a, b) a - b)否则你一定会被坑到怀疑人生。Java 的 Arrays.sort 对基本类型数组使用的是双轴快排对对象数组使用的是归并排序所以对象数组是稳定的。如果想对 List 排序用 Collections.sort 或者 list.sort 都可以同样要提供 Comparator。Python 的 sort 和 sorted 则非常友好list.sort(keylambda x: x[1], reverseTrue) 这种写法清晰直观而且 Python 的排序是稳定的还支持多级 key 排序key 返回元组即可。说实话不管用哪种语言核心思想都是一样的你要非常清楚默认行为是什么再决定要不要自定义规则。很多线上笔试环境用的是 JavaScript你要是不知道 arr.sort() 默认按字典序排序第一题就会挂而且是一头雾水地挂掉。4. 手写排序与排列生成不只是为了“考试”4.1 手写快排与归并的模板与复杂度验证有的学校机试或者某些比赛的初赛会禁止使用标准库的排序函数这时候你就必须能手写排序。不要觉得这很荒谬——它考察的是你对分治思想的理解深度以及代码实现的细节功底。手写快排有两个细节决定了成败基准选取和递归边界。基准选最左或最右元素在面对近乎有序的数据时容易退化到 O(n^2)稳妥的做法是“三数取中”——在首、中、尾三个位置选中间值做基准。递归边界则是当区间长度足够小比如 16 或 32时改用插入排序这能显著减少递归调用的开销。手写归并要注意的是合并时的边界处理。网上很多模板在边界上写错导致数组越界或者丢元素。这里提供一个我非常推荐的简洁版本void mergeSort(vectorint arr, int l, int r, vectorint tmp) { if (l r) return; int mid (l r) 1; mergeSort(arr, l, mid, tmp); mergeSort(arr, mid 1, r, tmp); int i l, j mid 1, k l; while (i mid j r) { if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i mid) tmp[k] arr[i]; while (j r) tmp[k] arr[j]; for (int p l; p r; p) arr[p] tmp[p]; }你注意到没有if 判断用的是 而不是 这是为了保证归并排序的稳定性。如果左半和右半有相同元素我们优先取左半的相等元素的相对顺序就不会被破坏。另外要留意 tmp 数组建议用全局变量或者传引用避免在递归函数内反复申请 vector 导致大量堆分配耗时。这个小细节在数据量 10^6 时差距非常明显——我试过局部申请 vector 比传全局引用慢了接近一倍。4.2 全排列生成的回溯模板与剪枝思路排列是另一个高频考点。最常见的需求是“生成 n 个元素的所有全排列”。最简单的实现方式是回溯DFS模板如下void dfs(vectorint nums, vectorbool used, vectorint path, vectorvectorint res) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); dfs(nums, used, path, res); path.pop_back(); used[i] false; } }这个模板可以生成所有排列但如果输入数组中有重复元素这个模板会生成大量重复排列。去重的方式是在同一层内跳过“值相同且之前那个副本没被用过”的元素。具体来说在循环遍历时加上一个条件if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue;这个条件的意思是如果当前元素和前一个元素值相等而且前一个还没被用过说明前一个是在更早的层级被用的那么当前这个就会产生与之前重复的分支直接减掉。这是排列生成去重最优雅的写法比用 set 去重快得多。但是要注意这个方法要求原数组有序所以你先要对 nums 进行 sort。这个细节很容易被忽略如果你不排序就直接跑去重条件里的 nums[i] nums[i-1] 只能保证相邻相等才跳过无序情况下相邻相等不代表整个序列里只有它们俩相等会漏结果。4.3 next_permutation 与 prev_permutation 的用法和原理C 标准库提供了 next_permutation 函数可以直接生成下一个字典序排列。用法非常简洁vectorint nums {1, 2, 3}; sort(nums.begin(), nums.end()); do { // 处理当前排列 } while (next_permutation(nums.begin(), nums.end()));它可以按字典序依次枚举所有排列。需要特别强调的是在使用 next_permutation 遍历所有排列之前数组必须是升序的。如果原始数组是 [3, 2, 1]直接调 next_permutation 会返回 false循环一次都不会执行。next_permutation 的原理其实很有价值它不是凭空生成而是在当前排列的基础上做最小的调整。大致思路是从右往左找到第一个“升序对”即满足 nums[i] nums[i1] 的位置 i然后在右侧从右往左找到第一个大于 nums[i] 的元素交换两者最后把 i1 到末尾这段反转。这就是“下一个排列”的标准算法。很多排列相关的题目会让你手写这个算法所以即使库函数好用原理也一定要吃透。Python 的 itertools.permutations 和 C 的 next_permutation 在实现上有差异前者是完全递归生成的可以按字典序输出但内存开销更大后者是原地修改数组的空间 O(1)。竞赛里如果允许用库next_permutation 显然是效率最高的选择。4.4 康托展开与逆康托展开排列与序号的桥梁有一类题目会问给定一个排列它是所有排列中第几个或者反过来给定序号求对应排列。这就是康托展开和逆康托展开的用武之地。它们是利用阶乘建立的编码体系在“排列状态压缩”中非常有用比如八数码问题、全排列哈希等。康托展开的公式是X a[n-1](n-1)! a[n-2](n-2)! ... a[1]*1! a[0]*0!其中 a[i] 表示第 i 位从右往左数0 为最低位在剩余未出现数字中的排名从 0 开始。实际实现时需要维护一个“还未使用的数字”集合每次取当前位置后面有多少个比它小的数乘上对应阶乘累加即可。逆康托展开则是把序号反推成排列用序号除以 (n-1)!商就是从剩余数字中取第几个取完从集合中移除余数继续处理低阶位。这个过程可以用树状数组或平衡树来维护剩余数字集合但 n 不大时直接用 vector 删除元素即可。了解康托展开的核心意义不在于背模板而在于建立“排列也是可计算的数字”这种直觉。很多搜索题里你需要记录一个排列状态是否被访问过康托展开就可以把全排列映射到连续整数区间让 visited 数组可以直接用 vector 声明省去 map 的开销。5. 排序在 ACM 场景的延伸MapReduce、外部排序与拓扑排序5.1 归并在大数据场景的延伸思考竞赛题中很少直接让你写一个 MapReduce 程序但“排序”作为一个思想体系它的延伸应用无处不在。MapReduce 框架里的 shuffle 阶段本质上就是在做一次大规模的分布式排序——map 输出的键值对按 key 分区、排序再交给 reduce 处理。其中涉及的核心思想就是“分治 归并”每个分区内部排序最后多路归并成一个全局有序的结果。这个思想在竞赛中对应的是“外部排序”问题如果数据量远超内存无法一次性读入并排序怎么办答案就是多路归并。把数据切分成多个小块每块在内存中排序后写回磁盘最后做 k 路归并。归并时用优先队列维护每个块的最小值就可以在 O(n log k) 的时间内完成整体排序。这个思路在很多“大数据模拟”题中出现过比如给定超大文件路径要求按内容排序你不可能真的一次性读入但你可以模拟归并的过程来解决。5.2 拓扑排序图上的“有向有序”拓扑排序在我个人看来是“排序”这个概念在图上最漂亮的一次延伸。它针对有向无环图把所有顶点排成一个线性序列使得对于每条有向边 (u, v)u 都排在 v 之前。拓扑排序并不是排序值的“大小”而是排序“依赖关系”。实现方式有经典两种Kahn 算法基于入度和 DFS基于完成时间。Kahn 算法更直观反复找出入度为 0 的顶点加入结果同时删除它出发的所有边更新邻接点入度。如果最后结果数量不等于总顶点数说明图中有环——拓扑排序只能用于 DAG检测环是它常用的一个副产品。还有一种很有意思的变体字典序最小的拓扑排序。只需要把 Kahn 算法中的“队列”换成“优先队列”每次取当前入度为 0 且编号最小的顶点即可。这在某些“课程安排”题目中是关键要求。DFS 版的拓扑排序则适合在递归处理中顺便做但要注意用三种状态标记未访问、访问中、已访问来检测环不然很容易死循环。5.3 稳定性在排序类题目中的关键作用我再重复一次稳定性真的是一个大坑。有的题目不会明说“稳定”但要求中隐含了稳定——比如按成绩降序输出成绩相同按学号升序。如果你直接 sort(persons.begin(), persons.end(), cmp)cmp 里写的是“先比成绩成绩相同比学号”这其实已经实现了多级排序不需要依赖稳定。但真正依赖稳定的场景是你分两次排序第二次的排序规则优先级更高。举个例子先按姓名排序再按年龄排序要求最终结果是“年龄升序同年龄按姓名排好”。如果直接用 std::sort 做两次排序第二次会把第一次的顺序打乱——因为 sort 是不稳定的。正确做法是使用 stable_sort它保证相等元素的相对顺序不变。这也是 std::stable_sort 存在的意义它在归并排序的基础上实现额外空间 O(n)。在竞赛中stable_sort 的使用频率确实不高但你一定要知道它的存在以及知道它对空间和时间的影响。如果只是为了让两个关键字形成组合排序直接用 tie 写在比较器里就好这是更简洁的方案不要画蛇添足。6. 常见问题与排查心得这些坑我都替你踩过了6.1 排序结果莫名错乱检查你的比较器是否满足严格弱序我在竞赛群里见过太多人问“为什么我的 sort 结果不对”最后排查出的原因几乎千篇一律比较器没有满足严格弱序。最快的自查方法是把数据量减小到 3-5 个元素手推一遍排序过程。如果发现元素之间出现了“循环比较”的矛盾比如 A 该排在 B 前B 该排在 C 前C 又该排在 A 前那么不稳定和越界问题就会随之而来。有一个非常典型的错误例子比较器写成 if (a b) return true; else return false。看起来没什么问题但如果 a 和 b 相等返回的是 false这符合要求。但如果写成 if (a b) return true; else return false那么相等时返回 true这相当于告诉 sort “a 可以排在 b 前面b 也可以排在 a 前面”标准的 std::sort 遇到这种比较器可能会把数组排乱极端情况下直接崩溃更准确地说未定义行为。所以记住比较器里严格使用 不要使用 。6.2 大数据量超时不是算法问题是 IO 和常数优化很多人写出正确的排序代码一提交就超时一脸懵。排查步骤我建议按这个顺序第一检查是否把 n10^6 的数据用插入排序或冒泡排序硬搞了。如果用的库函数 sort这个可能性不大。第二检查输入输出是否用了 cin/cout 而没有关闭同步。竞赛中加一句 ios::sync_with_stdio(false); cin.tie(nullptr); 或者直接改用 scanf/printf能把常数缩小好几倍。第三检查你的比较器是否过于复杂。如果在比较器里写了一个 O(n) 的遍历比如比较两个字符串时每次都算它们的某个特征函数那 sort 的总复杂度会变成 O(n^2 log n)再好也无法通过。我处理过很多次大数据超时最后定位到的原因往往不是排序本身而是预处理没做好。正确的做法是把每个元素的关键变量提前算好存进结构体比较器里只做 O(1) 的字段比较。此外向量扩容也是一个隐形陷阱如果知道数据量用 reserve 预留空间可以避免多次 memcpy 拷贝。6.3 next_permutation 漏解起始顺序必须是字典序最小这个问题很有意思我见过不止一个选手挂在“输出所有排列”上。他们写的是vectorint nums {3, 1, 2}; do { // 处理排列 } while (next_permutation(nums.begin(), nums.end()));结果只输出了 3 个排列而不是 6 个。原因很简单从 [3, 1, 2] 出发下一个排列是 [3, 2, 1]再下一个就没有了因为 [3, 2, 1] 是字典序最大的排列。所以这组循环只处理了两个排列加上初始的那个一共三个。正确做法是先 sort(nums.begin(), nums.end())让它变成 [1, 2, 3]再进入 do-while 循环。这个坑特别隐蔽因为代码逻辑上“循环直到 next_permutation 返回 false”看起来是对的但起始位置不是最小排列导致枚举不完整。如果你写的是 for 循环配合手动判断同样要注意初始排序。每次用 next_permutation 前务必确认序列是升序的。6.4 手写排序边界越界的检查方法手写排序的边界问题尤其是归并和快排是竞赛中调试最花时间的地方。我的经验是在本地跑一段随机测试数据然后用 std::sort 的结果作为基准对比。写一个简单的脚本生成 10000 组随机数组分别用手写排序和 std::sort 排序对比结果是否一致。如果不一致可以用二分法缩小数据量范围找到最小的出错样例然后单步调试。另外手写归并中最容易出错的是合并时左右边界的计算。我建议坚持“左闭右开”的区间约定也就是递归参数写成 mergeSort(arr, l, mid) 和 mergeSort(arr, mid, r)右边界不包含。这样 mid (l r) 1 后左半部分是 [l, mid)右半部分是 [mid, r)不会出现差一错误。初始调用写成 mergeSort(arr, 0, n)而不是 n-1。这套约定一旦习惯边界永远不可能越界。6.5 排序与排列题目的现场调试策略最后分享一个实战中的调试策略当一道题的输出结果和样例不一致时不要从头到尾逐行动态调试。先确认整体算法框架没问题然后构造一个 n 很小的输入比如 n3 或 n4把每一步的中间状态打印出来。排序题就打印每一次比较后的数组状态排列题就打印每一步递归的 path 和 used。这样做十分钟以内就能定位问题。另外我强烈建议在提交前做一个“边界值测试”空数组、单元素、全相同元素、逆序数组。这四种边界在排序和排列题当中非常容易暴露 bug。很多选手栽在“空数组”这种极端输入上坐标处理稍不小心就会越界。把常见边界数据点写成一个测试用例表每次写完代码都跑一遍能大幅提高一次通过率。7. 从排序到排列的系统构建我的竞赛实践建议7.1 建立“排序优先”的思考习惯我个人认为竞赛能力提升最快的方式就是在面对任何题目时先问自己一句这题能不能通过排序降低后续处理的复杂度举几个例子求区间重合问题排序后扫描一遍即可求两数之和等于定值排序后双指针收敛即可求滑动窗口中的中位数排序后的数据结构配合优先队列即可。排序不是一个孤立的知识点它是一个“预处理工具”。你做得多了就会发现很多看似复杂的问题一旦数据有序规律就浮现出来了。这种思考习惯需要在训练中刻意培养。比如你刷题时可以做一个记录这题第一步做了什么如果第一步是“将输入按某种规则排序”就在旁边标记一个 S。统计一个月之后你会发现 S 型题目的占比相当可观。到那个时候你对排序的理解就跳出了“怎么写”的层面进入了“什么时候用”的层面。7.2 排序与排列的联考形式带约束的排列数量问题我再展开一个非常常见的综合题型给定 n 个数有些数重复要求计算“满足某种约束的排列数量”。比如“使得所有相同元素不相邻”“使得逆序对数量恰好为 k”等。这种题目要求你把排序、排列、DP 串起来。拿“相同元素不相邻”举例思路是先统计每个元素的频次把出现次数最多的元素作为“骨架”插入再用其他元素在空隙中填充。另一种常见解法是容斥原理用所有排列减去“某种相邻性约束”的排列这又牵扯到排列生成和去重。这类题目在蓝桥杯等比赛的中等难度题中很常见考查的就是你能否灵活运用排列计数模型。排列计数背后还有一个常用于状态转移的工具——状压 DP。当 n 很小比如 n ≤ 15时可以用二进制位表示哪些元素已经排好DP[mask] 记录当前状态下满足条件的排列数。这个过程和全排列的 DFS 非常像只是用 DP 替代递归用状态去重替代回溯。理解全排列的生成过程对理解这类 DP 状态设计有直接的帮助。7.3 训练清单哪些排序排列题目值得反复刷很多新读者会问排序和排列我应该刷哪些题我整理了一个自己练过的清单难度从低到高排列每一道都值得反复做P1177 【模板】排序洛谷的经典模板题适合用来练习手写快速排序或归并排序这个题对边界的要求很严格适合检验模板是否熟练。P1059 明明的随机数排序 去重的入门题适合练习 sort 和 unique 的配合使用。P1781 宇宙总统大整数排序问题适合练习字符串转数值后的排序思路。P1008 三连击全排列加条件筛选的经典题适合练习用 next_permutation 生成排列并做条件判断。P1111 修复公路涉及拓扑排序或者排序后扫描的进阶题适合检验排序后贪心的套路是否熟练。UVA 120 Stacks of Flapjacks归并排序和翻转操作的组合题目适合练习操作类排序问题。Codeforces 1364C Ehab and Prefix MEX通过排序和映射构造序列适合练习隐含排序的思维题。7.4 小技巧优先队列在排序题中的妙用最后提一个小技巧。有些“排序题”并不要求你排完整个数组而是只要“最小的 k 个”或者“第 k 小”。这时候全排序就是浪费一个大小为 k 的最大堆就够了。具体做法是维护一个容量为 k 的大顶堆遍历所有元素时如果堆还没满就直接入堆如果堆顶大于新元素就替换堆顶。遍历结束后堆中就是最小的 k 个元素。时间复杂度 O(n log k)当 k 远小于 n 时性价比极高。这个技巧在“动态排序”场景下尤其好用系统实时插入新元素我们要随时知道当前最小的 k 个值这时候 std::priority_queue 是最简洁的方案。它比每次调用 sort 快得多也更好写。很多实时排行榜类的问题本质上就是“动态维护有序性”优先队列和堆就是排序在这个场景下的延伸。8. 个人经验总结写到这里回顾我自己的竞赛经历排序和排列确实贯穿了几乎所有比赛阶段。从最初学会写冒泡排序的兴奋到后来熟练掌握 std::sort 和各种排列生成技巧再到逐渐理解排序背后的分治、稳定性、桶思想、状态压缩等概念这一步一步的递进就是算法能力成长的一个缩影。如果要我给一条最实用的建议那就是标准库是你的第一选择除非题目明确禁止否则永远不要自己造轮子来替代编译器的优化。但与此同时你必须对库函数背后的原理了如指掌因为这才是你在面对变种题、非常规数据、极端约束时能保持底气的根源。排序不要只满足于“会调 sort”排列不要只停留在“会用 next_permutation”。有空的时候把手写快排、归并、康托展开、拓扑排序的经典实现各默写一遍速度会越来越快。竞赛这条路没有捷径但这些基础知识的扎实程度直接决定了你在难题面前能走多远。 排序与排列：算法竞赛选手的核心基本功与实战技巧
1. 排序与排列竞赛选手绕不开的核心基本功我接触算法竞赛这么多年最深的一个体会就是排序不是“会写”就行而是要在任何场景下都“信手拈来”。无论你是刚接触蓝桥杯、ICPC、Codeforces还是在应付各类机试和笔试排序和排列几乎是无处不在的——它可能是题目本身更多的是作为其他算法的前置步骤。很多看起来跟排序八竿子打不着的题最后都会归约到“先把数据排个序”这个动作上。所以竞赛圈里一直有句老话排序和排列是算法选手的“肌肉记忆”。这篇文章不打算把《算法导论》里所有的证明搬过来粘贴一遍而是从实际比赛和刷题的角度把排序、排列里面真正有价值、能帮你拿分的东西讲透。我会着重讲几个方面各种排序算法的原理和适用场景、竞赛中真正依赖的库函数用法、手写排序的模板以及背后的复杂度分析、排列的生成思路还有一组很容易被忽略但比赛中很常见的问题——拓扑排序。你会发现这些东西一旦串联起来它们彼此之间的关联非常紧密理解了这层关系很多题目在你眼里就会变得透明很多。2. 排序算法全景先搞清楚每种“武器”的脾气2.1 比较排序的家族谱系与复杂度下界排序算法大致可以分为两类基于比较的排序和不基于比较的排序。前者包括我们熟悉的冒泡、选择、插入、希尔、归并、快排、堆排后者主要是计数排序、基数排序和桶排序这几位“另类选手”。基于比较的排序有一个极其重要的理论结论在最坏情况下任何基于两两比较的排序算法时间复杂度都不可能低于 O(n log n)。这个结论的证明用的是决策树模型——n 个元素的排列有 n! 种可能而一次比较最多产生两个分支所以树的高度至少是 log(n!)由斯特林公式可知 n! 约等于 (n/e)^n取对数以后就是 O(n log n)。这个结论的意义在于当你看到一道题要求排序并且数据范围是 10^6 级别的你就不用费心思想什么神奇的比较排序能突破 O(n log n)——不存在这种可能老老实实选快排或者归并就好。但这并不意味着所有比较排序都“一样快”它们之间的常数因子差异很大。冒泡排序和选择排序是 O(n^2)一般在数据量超过 5000 的时候就已经能感觉到明显的延迟。插入排序虽然理论复杂度也是 O(n^2)但它在近乎有序的数据上表现极好可以跑到 O(n)所以很多工业级排序实现会把插入排序作为小规模数据的收尾手段。希尔排序则是插入排序的改进版通过增量分组让元素先“大致有序”再逐步细排它的复杂度分析在竞赛中基本不会涉及但在《算法导论》的习题里偶尔会出现。2.2 快排、归并、堆排竞赛中的“三大件”快速排序是竞赛中最常用的排序算法没有之一。它的核心思想是分治选一个基准元素pivot把小于它的放左边大于它的放右边然后递归处理左右两侧。平均时间复杂度 O(n log n)但最坏会退化成 O(n^2)原因在于如果每次选的 pivot 恰好是最大或最小元素分割就严重失衡了。标准库里的 sort 函数做了一件很重要的事它会在递归深度过深时切换为堆排序保证最坏情况下仍然是 O(n log n)。这就是“内省排序”策略也是为什么竞赛中我们很少手写快排——std::sort 已经帮你把坑填平了。归并排序的思路同样是分治但它是先递归到底再在回溯过程中合并两个有序序列。合并过程需要 O(n) 的额外空间这是它不如快排常用的主要原因。但归并排序有两个无可替代的优点稳定、适合外部排序。所谓稳定就是相等元素的相对顺序不会被破坏。有的题明确要求“当关键值相同时按输入顺序输出”这时候稳定排序就是唯一选择。另外归并排序是分治思想的绝佳载体很多涉及“逆序对”的题目标准解法就是在归并排序的合并阶段顺手计数。堆排序则有些特殊它利用完全二叉树的性质在 O(n log n) 时间内完成排序且不需要额外空间。不过因为它的常数较大实际比赛中很少直接用堆排序来给数组排序。堆真正发光发热的地方是“动态维护最值”——比如优先队列。所以我会把它归入“数据结构工具”而非“常用排序手段”。但你需要清楚它的实现原理因为“手写堆”在竞赛中仍然是可能出现的考点。2.3 线性排序的适用边界计数、基数、桶计数排序的思路非常暴力既然比较排序有 O(n log n) 的天花板那我干脆不比了直接用值域开数组统计每个值出现的次数然后按顺序输出。这样做的时间复杂度是 O(n k)其中 k 是值域范围。只要 k 的范围可控比如 10^6 以内这就是一个快到离谱的排序方式。但它有两个致命限制只能排整数如果值域太大比如 10^9开数组就不可行了需要配合离散化使用。基数排序则是计数排序的推广它把数字拆成若干“位”从低位到高位逐位进行稳定计数排序。复杂度是 O(d * n)d 是位数。适用于大整数、字符串按字典序等场景。桶排序则是把数据按区间分到若干个桶里每个桶内再单独排序最后合并。它适合数据分布比较均匀的浮点数排序。这里我有一个很实用的经验竞赛中真正用到线性排序的场景其实不多因为数据范围一般都受到限制。但理解它们的原理对解决“排序问题变种”极有帮助——比如你需要统计频率、需要按某种权重排序这些本质上都是“映射 排序”的组合。3. 赛场上的 sort 实战从入门到不翻车3.1 std::sort 的正确姿势与比较器写法在 C 竞赛编程里std::sort 是默认武器。它基于内省排序实现足够快足够稳。但我见过太多选手在比较器上翻车导致卒于排序。最典型的错误是比较器没有满足“严格弱序”条件结果程序直接崩溃或者返回随机结果。严格弱序strict weak ordering听起来很学术其实就三条规则反对称性a b 和 b a 不能同时成立、传递性a b 且 b c 则 a c、不可比等价性a 不小于 b、b 也不小于 a 时认为两者等价。一个经典的坑是“比较器中使用大于等于号”。你可能会想当然地写 return a b这在数学上看好像没问题但实际上它违反了反对称性——a b 和 b a 在 a 等于 b 时可以同时成立这意味着严格弱序被破坏。正确写法是 return a b或者更规范地用 lambda 让 sort 按你想要的顺序排列。再看一个常见需求结构体多关键字排序。比如有 n 个人要按年龄升序、年龄相同按姓名升序。新手喜欢写一堆嵌套的 if-else其实用 C 的 tie 可以一行解决。#include bits/stdc.h using namespace std; struct Person { int age; string name; }; int main() { vectorPerson persons {{23, Alice}, {20, Bob}, {23, Charlie}}; sort(persons.begin(), persons.end(), [](const Person a, const Person b) { if (a.age ! b.age) return a.age b.age; return a.name b.name; }); // 更优雅的写法 sort(persons.begin(), persons.end(), [](const Person a, const Person b) { return tie(a.age, a.name) tie(b.age, b.name); }); for (auto p : persons) cout p.age p.name \n; return 0; }tie 的比较规则就是“按成员顺序依次比较”第一个不同的成员决定结果。这比手写嵌套判断简洁太多而且不容易漏条件。3.2 结构体排序时 operator 重载的取舍结构体排序还可以通过重载小于运算符实现这样 sort 不需要额外传比较器代码看起来更整洁。这种方式适合那些“排序规则在数据结构定义里就确定好”的场景。struct Person { int age; string name; bool operator(const Person other) const { return tie(age, name) tie(other.age, other.name); } };需要注意的一点是如果重载了 operator那么“小于”的语义应当和题目要求的排序方向一致。如果你需要按年龄降序排却把 operator 重载成了升序那你还是得另写比较器或者用反向迭代器。我的建议是能用 lambda 的地方就用 lambda因为排序方向在调用处才最清楚写在结构体里反而限制了灵活性。只有当结构体被多个容器、多个算法复用排序规则完全统一时才值得重载 operator。还有一个很隐蔽的坑如果你用的是 C20 的“宇宙飞船运算符”语法上很方便但请务必确认比较顺序符合预期。总之不要为了炫技而牺牲可读性比赛中最重要的是代码正确且快速写完。3.3 字符串排序细节字典序与自然排序的陷阱字符串排序在竞赛中也极其常见。默认的字符串比较是基于字典序的即逐字符比较 ASCII 码。但这里有个容易踩坑的真实问题字符串“10”和“9”按字典序比较“10”会排在“9”前面因为字符 1 的 ASCII 码小于 9。如果题目要求按“数值”排序你必须先把字符串转成整数或者自定义比较器按长度、按数值位来比较。另外字符串排序还经常涉及“自定义排序规则”比如按字母频率、按字符串长度、按特殊字符优先级。这时候比较器里就不仅仅是直接比较字符串本身而是预处理出映射表后再比较。举个例子有一道很经典的字符串排序题给定一组单词要求按它们中“某个字符出现次数”的降序排列次数相同按字典序升序。这类题比较器的编写要特别小心尽可能把预处理结果存下来避免在比较器里重复计算导致超时。3.4 其他语言中的排序要点JS、Java、Python虽然 C 是竞赛主流但我发现很多读者在自学阶段用的是 JavaScript 或 Python。JS 的数组排序方法 sort 有一个大坑默认按字符串字典序排序所以 [10, 9, 100].sort() 的结果是 [10, 100, 9]而不是 [9, 10, 100]。必须显式传入比较函数 arr.sort((a, b) a - b)否则你一定会被坑到怀疑人生。Java 的 Arrays.sort 对基本类型数组使用的是双轴快排对对象数组使用的是归并排序所以对象数组是稳定的。如果想对 List 排序用 Collections.sort 或者 list.sort 都可以同样要提供 Comparator。Python 的 sort 和 sorted 则非常友好list.sort(keylambda x: x[1], reverseTrue) 这种写法清晰直观而且 Python 的排序是稳定的还支持多级 key 排序key 返回元组即可。说实话不管用哪种语言核心思想都是一样的你要非常清楚默认行为是什么再决定要不要自定义规则。很多线上笔试环境用的是 JavaScript你要是不知道 arr.sort() 默认按字典序排序第一题就会挂而且是一头雾水地挂掉。4. 手写排序与排列生成不只是为了“考试”4.1 手写快排与归并的模板与复杂度验证有的学校机试或者某些比赛的初赛会禁止使用标准库的排序函数这时候你就必须能手写排序。不要觉得这很荒谬——它考察的是你对分治思想的理解深度以及代码实现的细节功底。手写快排有两个细节决定了成败基准选取和递归边界。基准选最左或最右元素在面对近乎有序的数据时容易退化到 O(n^2)稳妥的做法是“三数取中”——在首、中、尾三个位置选中间值做基准。递归边界则是当区间长度足够小比如 16 或 32时改用插入排序这能显著减少递归调用的开销。手写归并要注意的是合并时的边界处理。网上很多模板在边界上写错导致数组越界或者丢元素。这里提供一个我非常推荐的简洁版本void mergeSort(vectorint arr, int l, int r, vectorint tmp) { if (l r) return; int mid (l r) 1; mergeSort(arr, l, mid, tmp); mergeSort(arr, mid 1, r, tmp); int i l, j mid 1, k l; while (i mid j r) { if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i mid) tmp[k] arr[i]; while (j r) tmp[k] arr[j]; for (int p l; p r; p) arr[p] tmp[p]; }你注意到没有if 判断用的是 而不是 这是为了保证归并排序的稳定性。如果左半和右半有相同元素我们优先取左半的相等元素的相对顺序就不会被破坏。另外要留意 tmp 数组建议用全局变量或者传引用避免在递归函数内反复申请 vector 导致大量堆分配耗时。这个小细节在数据量 10^6 时差距非常明显——我试过局部申请 vector 比传全局引用慢了接近一倍。4.2 全排列生成的回溯模板与剪枝思路排列是另一个高频考点。最常见的需求是“生成 n 个元素的所有全排列”。最简单的实现方式是回溯DFS模板如下void dfs(vectorint nums, vectorbool used, vectorint path, vectorvectorint res) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); dfs(nums, used, path, res); path.pop_back(); used[i] false; } }这个模板可以生成所有排列但如果输入数组中有重复元素这个模板会生成大量重复排列。去重的方式是在同一层内跳过“值相同且之前那个副本没被用过”的元素。具体来说在循环遍历时加上一个条件if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue;这个条件的意思是如果当前元素和前一个元素值相等而且前一个还没被用过说明前一个是在更早的层级被用的那么当前这个就会产生与之前重复的分支直接减掉。这是排列生成去重最优雅的写法比用 set 去重快得多。但是要注意这个方法要求原数组有序所以你先要对 nums 进行 sort。这个细节很容易被忽略如果你不排序就直接跑去重条件里的 nums[i] nums[i-1] 只能保证相邻相等才跳过无序情况下相邻相等不代表整个序列里只有它们俩相等会漏结果。4.3 next_permutation 与 prev_permutation 的用法和原理C 标准库提供了 next_permutation 函数可以直接生成下一个字典序排列。用法非常简洁vectorint nums {1, 2, 3}; sort(nums.begin(), nums.end()); do { // 处理当前排列 } while (next_permutation(nums.begin(), nums.end()));它可以按字典序依次枚举所有排列。需要特别强调的是在使用 next_permutation 遍历所有排列之前数组必须是升序的。如果原始数组是 [3, 2, 1]直接调 next_permutation 会返回 false循环一次都不会执行。next_permutation 的原理其实很有价值它不是凭空生成而是在当前排列的基础上做最小的调整。大致思路是从右往左找到第一个“升序对”即满足 nums[i] nums[i1] 的位置 i然后在右侧从右往左找到第一个大于 nums[i] 的元素交换两者最后把 i1 到末尾这段反转。这就是“下一个排列”的标准算法。很多排列相关的题目会让你手写这个算法所以即使库函数好用原理也一定要吃透。Python 的 itertools.permutations 和 C 的 next_permutation 在实现上有差异前者是完全递归生成的可以按字典序输出但内存开销更大后者是原地修改数组的空间 O(1)。竞赛里如果允许用库next_permutation 显然是效率最高的选择。4.4 康托展开与逆康托展开排列与序号的桥梁有一类题目会问给定一个排列它是所有排列中第几个或者反过来给定序号求对应排列。这就是康托展开和逆康托展开的用武之地。它们是利用阶乘建立的编码体系在“排列状态压缩”中非常有用比如八数码问题、全排列哈希等。康托展开的公式是X a[n-1](n-1)! a[n-2](n-2)! ... a[1]*1! a[0]*0!其中 a[i] 表示第 i 位从右往左数0 为最低位在剩余未出现数字中的排名从 0 开始。实际实现时需要维护一个“还未使用的数字”集合每次取当前位置后面有多少个比它小的数乘上对应阶乘累加即可。逆康托展开则是把序号反推成排列用序号除以 (n-1)!商就是从剩余数字中取第几个取完从集合中移除余数继续处理低阶位。这个过程可以用树状数组或平衡树来维护剩余数字集合但 n 不大时直接用 vector 删除元素即可。了解康托展开的核心意义不在于背模板而在于建立“排列也是可计算的数字”这种直觉。很多搜索题里你需要记录一个排列状态是否被访问过康托展开就可以把全排列映射到连续整数区间让 visited 数组可以直接用 vector 声明省去 map 的开销。5. 排序在 ACM 场景的延伸MapReduce、外部排序与拓扑排序5.1 归并在大数据场景的延伸思考竞赛题中很少直接让你写一个 MapReduce 程序但“排序”作为一个思想体系它的延伸应用无处不在。MapReduce 框架里的 shuffle 阶段本质上就是在做一次大规模的分布式排序——map 输出的键值对按 key 分区、排序再交给 reduce 处理。其中涉及的核心思想就是“分治 归并”每个分区内部排序最后多路归并成一个全局有序的结果。这个思想在竞赛中对应的是“外部排序”问题如果数据量远超内存无法一次性读入并排序怎么办答案就是多路归并。把数据切分成多个小块每块在内存中排序后写回磁盘最后做 k 路归并。归并时用优先队列维护每个块的最小值就可以在 O(n log k) 的时间内完成整体排序。这个思路在很多“大数据模拟”题中出现过比如给定超大文件路径要求按内容排序你不可能真的一次性读入但你可以模拟归并的过程来解决。5.2 拓扑排序图上的“有向有序”拓扑排序在我个人看来是“排序”这个概念在图上最漂亮的一次延伸。它针对有向无环图把所有顶点排成一个线性序列使得对于每条有向边 (u, v)u 都排在 v 之前。拓扑排序并不是排序值的“大小”而是排序“依赖关系”。实现方式有经典两种Kahn 算法基于入度和 DFS基于完成时间。Kahn 算法更直观反复找出入度为 0 的顶点加入结果同时删除它出发的所有边更新邻接点入度。如果最后结果数量不等于总顶点数说明图中有环——拓扑排序只能用于 DAG检测环是它常用的一个副产品。还有一种很有意思的变体字典序最小的拓扑排序。只需要把 Kahn 算法中的“队列”换成“优先队列”每次取当前入度为 0 且编号最小的顶点即可。这在某些“课程安排”题目中是关键要求。DFS 版的拓扑排序则适合在递归处理中顺便做但要注意用三种状态标记未访问、访问中、已访问来检测环不然很容易死循环。5.3 稳定性在排序类题目中的关键作用我再重复一次稳定性真的是一个大坑。有的题目不会明说“稳定”但要求中隐含了稳定——比如按成绩降序输出成绩相同按学号升序。如果你直接 sort(persons.begin(), persons.end(), cmp)cmp 里写的是“先比成绩成绩相同比学号”这其实已经实现了多级排序不需要依赖稳定。但真正依赖稳定的场景是你分两次排序第二次的排序规则优先级更高。举个例子先按姓名排序再按年龄排序要求最终结果是“年龄升序同年龄按姓名排好”。如果直接用 std::sort 做两次排序第二次会把第一次的顺序打乱——因为 sort 是不稳定的。正确做法是使用 stable_sort它保证相等元素的相对顺序不变。这也是 std::stable_sort 存在的意义它在归并排序的基础上实现额外空间 O(n)。在竞赛中stable_sort 的使用频率确实不高但你一定要知道它的存在以及知道它对空间和时间的影响。如果只是为了让两个关键字形成组合排序直接用 tie 写在比较器里就好这是更简洁的方案不要画蛇添足。6. 常见问题与排查心得这些坑我都替你踩过了6.1 排序结果莫名错乱检查你的比较器是否满足严格弱序我在竞赛群里见过太多人问“为什么我的 sort 结果不对”最后排查出的原因几乎千篇一律比较器没有满足严格弱序。最快的自查方法是把数据量减小到 3-5 个元素手推一遍排序过程。如果发现元素之间出现了“循环比较”的矛盾比如 A 该排在 B 前B 该排在 C 前C 又该排在 A 前那么不稳定和越界问题就会随之而来。有一个非常典型的错误例子比较器写成 if (a b) return true; else return false。看起来没什么问题但如果 a 和 b 相等返回的是 false这符合要求。但如果写成 if (a b) return true; else return false那么相等时返回 true这相当于告诉 sort “a 可以排在 b 前面b 也可以排在 a 前面”标准的 std::sort 遇到这种比较器可能会把数组排乱极端情况下直接崩溃更准确地说未定义行为。所以记住比较器里严格使用 不要使用 。6.2 大数据量超时不是算法问题是 IO 和常数优化很多人写出正确的排序代码一提交就超时一脸懵。排查步骤我建议按这个顺序第一检查是否把 n10^6 的数据用插入排序或冒泡排序硬搞了。如果用的库函数 sort这个可能性不大。第二检查输入输出是否用了 cin/cout 而没有关闭同步。竞赛中加一句 ios::sync_with_stdio(false); cin.tie(nullptr); 或者直接改用 scanf/printf能把常数缩小好几倍。第三检查你的比较器是否过于复杂。如果在比较器里写了一个 O(n) 的遍历比如比较两个字符串时每次都算它们的某个特征函数那 sort 的总复杂度会变成 O(n^2 log n)再好也无法通过。我处理过很多次大数据超时最后定位到的原因往往不是排序本身而是预处理没做好。正确的做法是把每个元素的关键变量提前算好存进结构体比较器里只做 O(1) 的字段比较。此外向量扩容也是一个隐形陷阱如果知道数据量用 reserve 预留空间可以避免多次 memcpy 拷贝。6.3 next_permutation 漏解起始顺序必须是字典序最小这个问题很有意思我见过不止一个选手挂在“输出所有排列”上。他们写的是vectorint nums {3, 1, 2}; do { // 处理排列 } while (next_permutation(nums.begin(), nums.end()));结果只输出了 3 个排列而不是 6 个。原因很简单从 [3, 1, 2] 出发下一个排列是 [3, 2, 1]再下一个就没有了因为 [3, 2, 1] 是字典序最大的排列。所以这组循环只处理了两个排列加上初始的那个一共三个。正确做法是先 sort(nums.begin(), nums.end())让它变成 [1, 2, 3]再进入 do-while 循环。这个坑特别隐蔽因为代码逻辑上“循环直到 next_permutation 返回 false”看起来是对的但起始位置不是最小排列导致枚举不完整。如果你写的是 for 循环配合手动判断同样要注意初始排序。每次用 next_permutation 前务必确认序列是升序的。6.4 手写排序边界越界的检查方法手写排序的边界问题尤其是归并和快排是竞赛中调试最花时间的地方。我的经验是在本地跑一段随机测试数据然后用 std::sort 的结果作为基准对比。写一个简单的脚本生成 10000 组随机数组分别用手写排序和 std::sort 排序对比结果是否一致。如果不一致可以用二分法缩小数据量范围找到最小的出错样例然后单步调试。另外手写归并中最容易出错的是合并时左右边界的计算。我建议坚持“左闭右开”的区间约定也就是递归参数写成 mergeSort(arr, l, mid) 和 mergeSort(arr, mid, r)右边界不包含。这样 mid (l r) 1 后左半部分是 [l, mid)右半部分是 [mid, r)不会出现差一错误。初始调用写成 mergeSort(arr, 0, n)而不是 n-1。这套约定一旦习惯边界永远不可能越界。6.5 排序与排列题目的现场调试策略最后分享一个实战中的调试策略当一道题的输出结果和样例不一致时不要从头到尾逐行动态调试。先确认整体算法框架没问题然后构造一个 n 很小的输入比如 n3 或 n4把每一步的中间状态打印出来。排序题就打印每一次比较后的数组状态排列题就打印每一步递归的 path 和 used。这样做十分钟以内就能定位问题。另外我强烈建议在提交前做一个“边界值测试”空数组、单元素、全相同元素、逆序数组。这四种边界在排序和排列题当中非常容易暴露 bug。很多选手栽在“空数组”这种极端输入上坐标处理稍不小心就会越界。把常见边界数据点写成一个测试用例表每次写完代码都跑一遍能大幅提高一次通过率。7. 从排序到排列的系统构建我的竞赛实践建议7.1 建立“排序优先”的思考习惯我个人认为竞赛能力提升最快的方式就是在面对任何题目时先问自己一句这题能不能通过排序降低后续处理的复杂度举几个例子求区间重合问题排序后扫描一遍即可求两数之和等于定值排序后双指针收敛即可求滑动窗口中的中位数排序后的数据结构配合优先队列即可。排序不是一个孤立的知识点它是一个“预处理工具”。你做得多了就会发现很多看似复杂的问题一旦数据有序规律就浮现出来了。这种思考习惯需要在训练中刻意培养。比如你刷题时可以做一个记录这题第一步做了什么如果第一步是“将输入按某种规则排序”就在旁边标记一个 S。统计一个月之后你会发现 S 型题目的占比相当可观。到那个时候你对排序的理解就跳出了“怎么写”的层面进入了“什么时候用”的层面。7.2 排序与排列的联考形式带约束的排列数量问题我再展开一个非常常见的综合题型给定 n 个数有些数重复要求计算“满足某种约束的排列数量”。比如“使得所有相同元素不相邻”“使得逆序对数量恰好为 k”等。这种题目要求你把排序、排列、DP 串起来。拿“相同元素不相邻”举例思路是先统计每个元素的频次把出现次数最多的元素作为“骨架”插入再用其他元素在空隙中填充。另一种常见解法是容斥原理用所有排列减去“某种相邻性约束”的排列这又牵扯到排列生成和去重。这类题目在蓝桥杯等比赛的中等难度题中很常见考查的就是你能否灵活运用排列计数模型。排列计数背后还有一个常用于状态转移的工具——状压 DP。当 n 很小比如 n ≤ 15时可以用二进制位表示哪些元素已经排好DP[mask] 记录当前状态下满足条件的排列数。这个过程和全排列的 DFS 非常像只是用 DP 替代递归用状态去重替代回溯。理解全排列的生成过程对理解这类 DP 状态设计有直接的帮助。7.3 训练清单哪些排序排列题目值得反复刷很多新读者会问排序和排列我应该刷哪些题我整理了一个自己练过的清单难度从低到高排列每一道都值得反复做P1177 【模板】排序洛谷的经典模板题适合用来练习手写快速排序或归并排序这个题对边界的要求很严格适合检验模板是否熟练。P1059 明明的随机数排序 去重的入门题适合练习 sort 和 unique 的配合使用。P1781 宇宙总统大整数排序问题适合练习字符串转数值后的排序思路。P1008 三连击全排列加条件筛选的经典题适合练习用 next_permutation 生成排列并做条件判断。P1111 修复公路涉及拓扑排序或者排序后扫描的进阶题适合检验排序后贪心的套路是否熟练。UVA 120 Stacks of Flapjacks归并排序和翻转操作的组合题目适合练习操作类排序问题。Codeforces 1364C Ehab and Prefix MEX通过排序和映射构造序列适合练习隐含排序的思维题。7.4 小技巧优先队列在排序题中的妙用最后提一个小技巧。有些“排序题”并不要求你排完整个数组而是只要“最小的 k 个”或者“第 k 小”。这时候全排序就是浪费一个大小为 k 的最大堆就够了。具体做法是维护一个容量为 k 的大顶堆遍历所有元素时如果堆还没满就直接入堆如果堆顶大于新元素就替换堆顶。遍历结束后堆中就是最小的 k 个元素。时间复杂度 O(n log k)当 k 远小于 n 时性价比极高。这个技巧在“动态排序”场景下尤其好用系统实时插入新元素我们要随时知道当前最小的 k 个值这时候 std::priority_queue 是最简洁的方案。它比每次调用 sort 快得多也更好写。很多实时排行榜类的问题本质上就是“动态维护有序性”优先队列和堆就是排序在这个场景下的延伸。8. 个人经验总结写到这里回顾我自己的竞赛经历排序和排列确实贯穿了几乎所有比赛阶段。从最初学会写冒泡排序的兴奋到后来熟练掌握 std::sort 和各种排列生成技巧再到逐渐理解排序背后的分治、稳定性、桶思想、状态压缩等概念这一步一步的递进就是算法能力成长的一个缩影。如果要我给一条最实用的建议那就是标准库是你的第一选择除非题目明确禁止否则永远不要自己造轮子来替代编译器的优化。但与此同时你必须对库函数背后的原理了如指掌因为这才是你在面对变种题、非常规数据、极端约束时能保持底气的根源。排序不要只满足于“会调 sort”排列不要只停留在“会用 next_permutation”。有空的时候把手写快排、归并、康托展开、拓扑排序的经典实现各默写一遍速度会越来越快。竞赛这条路没有捷径但这些基础知识的扎实程度直接决定了你在难题面前能走多远。