算法竞赛排序与排列全解析：从STL sort到逆康托展开

打算法竞赛的人早晚都会在“排序和排列”这里栽一次跟头。我说的栽不是不会用sort而是排得不够聪明——碰到逆序对、第k大、拓扑序、康托展开、多关键字排序这些变体就直接懵了。排序作为最基础的算法板块几乎是所有题目的土壤很多难题剥开外壳内里就是一套精心改装的排序逻辑。今天这篇就围绕算法竞赛中的排序与排列做一次彻底整理从STL sort的底层逻辑讲到逆康托展开的推导路径把我实测过的模板代码、踩过的坑、调过的bug全铺开来。适合刚入竞赛圈想系统梳理排序板块的人也适合刷题遇到排序变体卡壳的老选手当手册翻。我先把这三年刷题过程中跟排序相关的题目归了个类发现翻来覆去就那几个考法直接排序占四成、结构体多关键字排序占两成、归并求逆序对和分治思想占一成半、排列枚举和康托展开占一成、拓扑排序及差分约束占一成半。这个分布说明排序板块的复习不能只停留在“会调sort”得把底层原理、自定义比较器、排列组合的映射关系以及依赖排序的算法串起来才能真正形成战斗力。1. 排序算法竞赛的地基工程1.1 为什么排序在竞赛中是“万能工具”排序的价值远不止“让数据有序”这层表面意思。很多看似跟排序无关的题目往里挖几层就能看到排序的影子求一组数的中位数、众数、第k小排序后下标直接定位。区间问题合并区间、区间交集按左端点排序后一趟扫描就能完成合并。贪心题几乎都依赖排序来确定最优处理顺序比如活动安排、任务调度、最小延迟。逆序对、离散化、差分数组的坐标压缩本质是排序 二分查找。二分答案 check 部分经常要排序后贪心验证。图的拓扑排序DAG上的一种“依赖关系线性化”也是排序思想在非数值域的延伸。我可以直接说排序算法是竞赛考纲里投入产出比最高的一块。你哪怕只把sort用好、把归并排序的逆序对写法背下来就已经能解决很多银牌以下难度的排序相关题。1.2 竞赛选手的排序算法选型表不同场景要选不同算法不能一把sort走天下。下面这张表是我自己刷题时的选型逻辑基本覆盖了竞赛里所有排序需求应用场景推荐算法时间复杂度稳定性额外空间理由常规数值排序内省排序STL sort平均O(n log n)不稳定O(log n)常数极小综合最强求逆序对 / 归并思想归并排序O(n log n)稳定O(n)分治过程天然统计逆序大范围小值域计数排序 / 桶排序O(n k)稳定O(k)值域k较小时碾压O(n log n)字符串字典序基数排序配合计数O(n * L)稳定O(n k)按位排序避免O(nL log n)小规模数据n 50插入排序O(n^2)稳定O(1)常数小代码短需要原地稳定排序表排序 / 原地归并O(n log n)稳定O(1)竞赛极少数要求需手写依赖关系线性化拓扑排序O(n m)天然稳定O(n)在DAG上按入度驱动我实测下来的结论是90%的题用STL的sort就够了剩下的10%也多半是“归并排序求逆序对”或“自定义排序规则”。如果对排序算法理解停留在“sort能排”的阶段很多衍生题会卡住——比如让你手写快排的正反序、让排序支持自定义规则、让排序在O(n)里完成这些一旦碰到就会露怯。2. 六大排序算法的原理拆解与代码模板2.1 快速排序最锋利的双刃剑快排的核心思想是分治 基准划分。每次选一个基准元素x把序列切成两半左半都小于等于x右半都大于等于x然后递归处理左右两半。关键在于它不像归并排序那样需要额外的合并数组而是原地完成划分。我给竞赛用的快排模板是下面这个采用“边界法”写法比教科书常见的Lomuto分区更好用void quickSort(int a[], int l, int r) { if (l r) return; int i l - 1, j r 1; int pivot a[(l r) 1]; // 取中点规避有序数据的退化 while (i j) { do i; while (a[i] pivot); do j--; while (a[j] pivot); if (i j) { swap(a[i], a[j]); } } quickSort(a, l, j); quickSort(a, j 1, r); // 注意递归边界是j不是i }很多人手写快排容易写挂我踩过的坑主要有两个坑1递归边界选错。如果用quickSort(a, l, i - 1)在某些划分情况下会直接越界死循环。建议记住“以j为界左边递归 [l, j]右边递归 [j1, r]”同时配合取中点基准。坑2比较符号不能随意改。while (a[i] pivot)与while (a[j] pivot)必须是一避一虚。如果改成当数组里存在大量重复元素时i和j会一直交替跨越导致递归深度爆炸实测直接爆栈。快排的复杂度平均O(n log n)最好也是O(n log n)但最坏是O(n^2)——比如每次划分都极其不均衡。STL的sort不是单纯快排它用的是内省排序递归深度超过一定阈值后自动切换到堆排序保证最坏复杂度也是O(n log n)。所以竞赛中强烈建议直接调sort而不是自己写快排。2.2 归并排序稳定且附带逆序对归并排序的思路是“先分到底再两两合并”。它满足稳定排序的定义值相等的元素在排序前后相对顺序不变。这个稳定性在后面讲结构体排序时非常关键。更重要的是归并排序在合并过程中可以顺带统计逆序对数量。逆序对就是满足i j且a[i] a[j]的数对求它的经典场景是逆序对计数题、冒泡排序交换次数题、求数组“有序程度”的题。long long mergeSortCnt 0; void mergeSort(int a[], int l, int r) { if (l r) return; int mid (l r) 1; mergeSort(a, l, mid); mergeSort(a, mid 1, r); int i l, j mid 1, k 0; int tmp[r - l 1]; while (i mid j r) { if (a[i] a[j]) { tmp[k] a[i]; } else { // 左半剩余元素都比a[j]大每个都能形成逆序对 mergeSortCnt mid - i 1; tmp[k] a[j]; } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (i l; i r; i) a[i] tmp[i - l]; }注意逆序对数量可能非常大n为10^5时最坏约5×10^9个数对所以统计变量要用long long否则会溢出WA这是很多新人容易忽略的点。用归并排序的另一个好处是它天然支持“第k小”的另一种解法思路归并的过程中你其实是在维护两个有序区间对“跨区间第k小”这种题可以用归并的思想写出复杂度很稳的解法。2.3 计数排序与基数排序突破O(n log n)天花板的利器当值域k远小于n log n时排序耗时的上限其实取决于值域。计数排序的思路非常简单用一个数组cnt[]统计每个值出现的次数然后按值从小到大把元素依次放回原数组。void countingSort(int a[], int n, int maxVal) { vectorint cnt(maxVal 1, 0); for (int i 0; i n; i) cnt[a[i]]; int idx 0; for (int v 0; v maxVal; v) { while (cnt[v]--) a[idx] v; } }计数排序的前提是值域非负且不太大。如果值域是负数或特别大需要先做偏移/离散化。竞赛中计数排序最常出现的位置是桶排序的前置步骤、基数排序的按位排序、以及数组元素是0~10^5范围的排序题。基数排序则是按个位、十位、百位……逐位进行计数排序。每次排序必须稳定否则前面位的顺序会被打乱。字符串字典序排序也可以用类似思想从末位字符往前稳定排序。不过竞赛里字符串排序通常直接用sort定字典序只有数据量极大、长度很长时才会上基数排序。2.4 选择排序与插入排序O(n^2)算法的现实意义选择排序和插入排序虽然在大数据量上不如O(n log n)算法但在竞赛里依然有存在感选择排序的循环不变量是每轮循环结束后序列前i个位置已经是全局最小/最大的i个元素且已就位。这个不变量在很多证明题里会考CLRS里就有让验证选择排序循环不变量的题目。我自己也拿它当过推导模板写数学证明比快排好写很多。插入排序适用于近乎有序的数据。n很小时插入排序的常数比快排还小所以STL的内省排序在递归到小区间通常th 16时会切到插入排序。选择排序的优势是交换次数少最坏也就O(n)次交换对“交换代价极大”的模拟题有用比如只能相邻交换的场景。希尔排序是插入排序的增量改良版核心是按gap分组做插入排序出现于考研笔试和部分原理题。竞赛里几乎不会让你写希尔排序但你要能说出gap的序列选择通常最终gap1时就是完整的插入排序以及它为什么能把大元素更快地往后挪。3. 排列与组合next_permutation背后的一整套思维3.1 next_permutation与prev_permutation的原理与手写实现C的next_permutation在算法竞赛中用途很广枚举全排列、验证对称性、暴力枚举组合顺序等。大部分人会调库但少数题会要求你手写或不让你用库所以必须理解底层逻辑。求下一个排列的核心思想是三步从右向左找到第一个升序对a[i] a[i1]这个i就是“临界点”。在[i1, n-1]中从右向左找到第一个大于a[i]的元素a[j]交换a[i]与a[j]。将[i1, n-1]反转变成升序因为此时右侧是降序反转后就是最小的字典序。bool nextPermutation(int a[], int n) { int i n - 2; while (i 0 a[i] a[i 1]) i--; // 找升序对 if (i 0) return false; // 整体降序已是最后一个 int j n - 1; while (a[j] a[i]) j--; // 找第一个大于a[i]的 swap(a[i], a[j]); reverse(a i 1, a n); return true; }prev_permutation就是对称操作找降序对a[i] a[i1]再找第一个小于a[i]的数交换最后反转右侧。这两个函数配合可以很方便地在BigInteger场景下实现排列枚举而不需要递归回溯。实战心得用next_permutation时一定要把原数组先sort成升序否则枚举只能得到从当前排列开始的后续排列会漏项。另外重复元素不用慌next_permutation会自动跳过重复排列——它本质上按字典序生成相同元素的排列不会重复输出但代价是你需要先对数组排序且不能手动去重否则容易错。3.2 康托展开与逆康托展开排列的编号化很多排列相关的题目要求你快速知道一个排列在所有排列里的字典序排名第几个或者知道第k个排列长什么样。这时候康托展开就是标准解法。康托展开公式X a[n-1] * (n-1)! a[n-2] * (n-2)! ... a[1] * 1! a[0] * 0!其中a[i]是第i位右侧比它小的数的个数。得到的X从0开始计数就是当前排列的字典序排名在0-index下。int fact[15]; // 预处理阶乘 int cantorExp(int a[], int n) { int ans 0; for (int i 0; i n; i) { int cnt 0; for (int j i 1; j n; j) if (a[j] a[i]) cnt; ans cnt * fact[n - 1 - i]; } return ans; // 从0开始如果要1-based排名就1 }逆康托展开则是给定排名k求出对应的排列。思路是逐步确定每一位void cantorInverse(int n, int k, int res[]) { vectorint remain; for (int i 1; i n; i) remain.push_back(i); for (int i 0; i n; i) { int f fact[n - 1 - i]; int idx k / f; k % f; res[i] remain[idx]; remain.erase(remain.begin() idx); } }注意逆康托展开要先把k处理为从0计数。实测用vector.erase的复杂度是O(n)n范围到12以内没问题n到20以上就该用树状数组优化了否则会TLE。竞赛中康托展开最常见的场景是把排列状态做哈希压缩作为状态压缩BFS/DFS的维度比如八数码问题、华容道、全排列的IDDFS等。3.3 拓扑排序依赖关系的线性化拓扑排序是对DAG有向无环图的顶点做线性排序使得对每条有向边u, vu都排在v之前。这不是传统意义上按值排序但它的本质也是“给出一个满足约束的顺序”因此我把它放进排序这一大板块里一起讲。热词里“拓扑排序”好几次出现说明大家刷题时对它确实头皮发麻。最常用的是Kahn卡恩算法基于入度统计vectorint topo(int n, vectorint g[]) { vectorint indeg(n 1, 0), res; for (int i 1; i n; i) for (int v : g[i]) indeg[v]; queueint q; for (int i 1; i n; i) if (indeg[i] 0) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); res.push_back(u); for (int v : g[u]) { if (--indeg[v] 0) q.push(v); } } // 如果res.size() n说明图里有环 return res.size() n ? res : vectorint{}; }如果要求输出字典序最小的拓扑序列把queue换成priority_queue小根堆即可。这是经典考法比如“给定一系列课程依赖关系输出一个合法修课顺序并要求字典序最小”洛谷的P1113和P4017都有类似思想。拓扑序还可以用来做最长路径、统计DAG上从起点到终点的路径数、差分约束系统的可行性判断等。它的应用远不止“排课表”竞赛里的DP依赖、状态转移顺序都可以先用拓扑排序把状态排好保证DP时前面的状态都已算出。另外提醒拓扑排序的DFS实现白灰黑三色标记法也要掌握。当题目要求你判断“是否存在唯一拓扑序”时每次出队时如果queue里超过一个元素说明拓扑序不唯一。这个判断逻辑Kahn算法直接就能给出来很多题就爱考这个。4. 排序的高级应用与实战套路4.1 结构体排序与多关键字排序竞赛中最常见的排序场景不是排整数而是排结构体。比如排成绩总分高的在前总分相同则语文高的在前语文再相同则学号小的在前。这个需求就是典型的多关键字排序。实现方式有三种我按推荐度排推荐方式1lambda表达式C11及以上struct Student { string name; int total, chinese, id; }; sort(stu, stu n, [](const Student a, const Student b) { if (a.total ! b.total) return a.total b.total; if (a.chinese ! b.chinese) return a.chinese b.chinese; return a.id b.id; });推荐方式2重载运算符struct Student { int total, chinese, id; bool operator (const Student o) const { if (total ! o.total) return total o.total; // 注意这里转成“更优则更小” if (chinese ! o.chinese) return chinese o.chinese; return id o.id; } }; sort(stu, stu n); // 默认调用operator推荐方式3函数对象死板但直观bool cmp(const Student a, const Student b) { ... } sort(stu, stu n, cmp);这里有一个核心认知sort的compare函数表示的是“a是否排在b前面”而不是“a是否大于b”。换言之它是严格弱序strict weak ordering。如果写成return a.total b.total当两个元素总分相等时比较器对(a,b)和(b,a)都会返回true这违反严格弱序规则会导致排序结果未定义甚至直接RE。这个坑太经典了我至少见过十次新人踩中。4.2 排序与二分、双指针的联动排序常常不是终点而是预处理。一个典型套路是“排序 二分 双指针”三件套用来解决很多看似困难的数组类问题。举例求两个有序数组的交集。先排序其中一个数组遍历另一个数组时用二分查找判断元素是否存在复杂度O(n log n)。如果两个数组都排序则双指针O(n)搞定。这类题在面试和校内赛中都很常见。举例ThreeSum问题三数之和。先排序然后固定一个数剩下的区间用双指针首尾逼近。复杂度从暴力的O(n^3)降到O(n^2)。没有排序双指针根本没法用。举例最长上升子序列LIS的O(n log n)解法。本质是维护一个有序数组每次用二分查找找到第一个大于等于当前元素的位置并替换。这个解法背后其实也是一个“排序 有序维护”的思想。理解了它就理解了很多同类DP优化题的套路。这里有一个值得强化的观念排序给你带来了“单调性”而单调性是二分的前提。很多题不排序就得贪心排序后就能二分甚至O(n)双指针。我在解题时养成了习惯任何提到“最大”“最小”“找第k个”的题目都先问自己一句——排序之后会不会变得更简单4.3 分布式排序思想从MapReduce到分组排序热词里有一大串和MapReduce排序相关的内容比如“mapreduce排序-倒排序索引”“mapreduce排序—分组排序”。这些虽然是大数据领域的词但核心排序思想跟竞赛里的“按Key排序 分组聚合”高度一致Map阶段按key把数据分发到不同桶/分区。Shuffle阶段对每个分区内的key做排序。Reduce阶段数据在reduce端按key有序到达方便做分组聚合。竞赛中的“分组排序”思维也类似先按组号排序组内再按价值排序这样一个sort调用就能把“先分组再排组内”的需求完成。实现方式是对结构体的第一关键字设为组号第二关键字设为价值。这比“先分组再分别排”的代码更简短也更好调。倒排索引的热词用排序来实现就很简单文档 - 单词的映射是正排单词 - 文档列表的映射是倒排。要生成倒排索引把每个单词映射到文档ID后对单词排序相同单词自然聚在一起再顺带记录文档ID列表。这本质上是“排序后相同的值相邻”这个性质的利用——很多题都是靠这个性质省去哈希表的。4.4 字符串排序的细节字符串排序在竞赛中非常常见。默认的sort对string数组排序是按字典序lexicographical order排的也就是逐个字符比较。这个性质用于求字典序最小/最大、按字典序枚举排列等场景非常顺手。但有两个变体要注意变体1按长度排序。例如用户名单按名字长度升序长度相同再按字典序。直接用lambdareturn a.length() ! b.length() ? a.length() b.length() : a b;变体2拼接最小字典序。经典题给定一堆数字字符串让你拼接成一个最小的数字字符串。比如[3,30,34,5,9]正确的拼接是3033459。这题如果用默认字典序排结果会是[3,30,34,5,9]拼接成3303459比正确结果大。正确做法是自定义比较器return a b b a;——判断两个字符串谁该在前直接比较拼接结果。这个“拼接比较”的技巧能解决一大类排序题。Java与JavaScript的差异提醒如果读者平时用Java要注意Arrays.sort对String[]是按字典序排的而如果是char[]则按字符编码。JavaScript的Array.sort()默认把元素转成字符串再按字典序排所以数字排序必须传(a, b) a - b不传默认排序会得到[1, 10, 2]这种结果。这些跨语言差异在面互联网公司笔试时也常被拿出来烤。5. 常见问题与排查技巧实录5.1 快排退化与TLE的排查手写快排或某些依赖递归排序的题最常遇见的故障是运行超时TLE。我用过的排查思路如下按优先级排序第一查基准选择。如果每次取a[l]作为基准而原数据已经有序快排每次划分都极度不均递归深度O(n)表现直接变成O(n^2)。解决取(l r) 1或随机索引作为基准。竞赛评测数据通常包含“卡快排模板”的构造数据所以基准不能写死。第二查递归边界。如果递归边界写错会导致无限递归或数组越界。我常用的安全套路是if (l r) return;然后以j为划分边界递归左右两侧。第三查比较符号。重复元素多时如果用了可能会让左右划分直接相互跨越导致死循环或巨慢。记住快排经典写法里的和就是刻意为了把相等元素分散到两侧而不是堆到一边。关于STL sort的底层STL的sort实现是内省排序一般来说不需要担心退化但如果你自定义了不合法的比较器STL sort的行为是未定义的可能直接段错误。如果sort出现莫名其妙RE先检查比较器是否满足严格弱序这是我最常排查出的原因。5.2 自定义比较器的四个隐蔽坑自定义比较器是排序题最容易翻车的地方我总结出四个高频坑坑错误示范正确示范使用了或return a.total b.total;return a.total b.total;升序未处理完全相等比较函数从不返回false所有字段相等时返回false用减法比较可能溢出return a.value - b.value;return a.value b.value;对浮点数直接用return a.f b.f;精度问题用eps或比较整数表示其中“减法溢出”这个坑最隐蔽。你写return a.value - b.value 0;时如果a.value 2^31 - 1b.value -2^31相减的结果会溢出成负数排序结果完全是错的。虽然让比较器返回true/false比返回整数更符合sort的要求但初学C的人很容易从Java的compareTo惯性里带出减法的写法。5.3 排序稳定性在多关键字场景下的价值排序稳定性指的是值相等的元素排序后相对顺序保持原样。竞赛里很多题会隐含要求稳定性。比如先按学号排再按成绩排你期望“成绩相同则按学号升序”——如果第二次排序是稳定排序你就不用额外写学号比较逻辑了。可STL的sort是不稳定的它的等价元素顺序无法保证。想要稳定排序必须使用stable_sort底层是归并排序或者把稳定性的要求写进比较器里。我踩过一个坑一道题要求“排名并列时按输入顺序输出”我先按分数sort了一次再尝试stable_sort按输入的id排结果发现第一次的sort已经把相对顺序打乱了第二遍stable_sort根本救不回来最后只能改成一个比较器同时比较分数和输入顺序。这就是稳定性最痛的教训如果你需要在多关键字排序中保留某种相对顺序直接把所有关键字全部写进同一个比较器千万别指望连续sort两次。5.4 字符串排序在中文与混合字符处理时的陷阱中文排序不是简单的sort能搞定的因为中文字符的Unicode编码和拼音/笔画没有直接对应关系。竞赛题目如果涉及中文排序通常会给一个明确的规则如按拼音首字母、按笔画这时候你要自己把规则映射成ASCII码或拼音串再做排序。曾经碰到一道“按省份字典序排序”的题很多人直接用s[0]的编码排结果“湖南”排在“湖北”前面——因为“南”和“北”的拼音首字母都不对。正确做法是维护一张省份到拼音串的映射按拼音串排序。另一个陷阱是混合数字字母字符排序。例如车牌号“A1B2”与“A10C”如果你按字符串字典序排“A10C”会排在“A1B2”之前因为0 B。如果业务上要按数字段做数值排序必须先将数字部分提取出来转int再参与比较。这类“字母数字组合的排序”在热词里出现过很多次大家在练习时别掉进“默认字典序正确排序”的惯性里。5.5 大数据量与IO优化对排序性能的影响当n到达10^6甚至更大时排序算法本身的时间复杂度固然重要但真正拖累速度的往往是读写和内存分配。我实测过几个优化点第一用scanf/printf或ios::sync_with_stdio(false)。数据规模一大cin不带优化会直接TLE这不是排序算法的锅是IO的锅。这个老生常谈但还是有很多人会忽略。第二避免频繁vector拷贝。归并排序直接开一个全局tmp数组不要在递归函数里反复新建vector。实测局部vector在大数据量下能比全局数组慢两倍因为每次合并都要重新分配堆内存。第三能用sort别手写快排。我并不是反对大家理解原理而是STL的sort在工程层面做了大量优化小规模切插入排序、快排深度阈值切堆排、三数取中基准选择自己手写的版本很难全面碾压它。需要手写排序的场景一定是库函数做不到比如求逆序对归并、稳定排序stable_sort也行、需要位级基数排序等。6. 实战模板一套通用的竞赛排序框架这里我给出一个我在比赛中实际用的排序代码框架可以直接抄作业。它涵盖了一维数组排序、结构体排序、逆序对、排列枚举和拓扑排序五类最常见需求。比赛时候直接拿出来改参数就能用。#include bits/stdc.h using namespace std; // 1. 一维数值排序升序 int arr[100005]; sort(arr, arr n); // 2. 一维数值降序 sort(arr, arr n, greaterint()); // 3. 结构体多关键字排序lambda版 struct Node { int val, id, tag; }; Node nodes[100005]; sort(nodes 1, nodes n 1, [](const Node a, const Node b) { if (a.val ! b.val) return a.val b.val; // 主关键字升序 if (a.id ! b.id) return a.id b.id; // 次关键字升序 return a.tag b.tag; // 第三关键字升序 }); // 4. 归并排序求逆序对模板见2.2节 long long inversionCount(int a[], int l, int r) { // 直接用mergeSortCnt全局变量累积 } // 5. 全排列枚举先sort再do-while sort(nodeArr, nodeArr n); do { // 处理当前排列 } while (next_permutation(nodeArr, nodeArr n)); // 6. 拓扑排序返回空vector表示存在环 vectorint topologicalSort(int n, vectorint g[]) { // 模板见3.3节 }这个框架里的代码我建议你别直接裸背先把各种边界条件脑内跑几遍。真正比赛时拼的是“丑陋但正确”的模板不是花哨的写法。我见过有人为了炫技把排序题写出各种花来最后边界用例挂了直接送人头。我自己还习惯在每个模板前面加一行注释标注对应题型的典型特征词比如“看到求逆序对 - 归并排序”“看到字典序最小拓扑 - priority_queue版Kahn”。这样比赛时翻模板文件如果允许带纸质材料能秒定位。平时刷题时把这个模板体系维护好比赛时就是降维打击。7. 我踩过的最深的几次坑排序这个板块看起来简单但实际比赛里因为排序细节丢分的案例我见的太多了。分享两件印象深的事。一次是用stable_sort连续排序期望保留第二关键字的顺序结果第一遍用的是sort把相对顺序全打乱了。那次我调了快一个小时最终才意识到问题出在排序稳定性上。从那以后凡是“多关键字排序”的题我全部写进一个比较器不搞两次排序的骚操作。这个教训在5.3节里已经提到再次强调一次它值得进我的top3花式翻车现场。另一次是手写快排时基准选a[l]评测数据构造了完全升序的数组直接给我表演了一个O(n^2)超时。那次我才真正理解排序算法的“复杂度”和“实际表现”之间隔着巨大的常数鸿沟乱选基准的快排遇上奇奇怪怪的评测数据真的会挂得体无完肤。从那以后我所有手写排序都默认“取中点基准 双指针划分”并且能用STL sort就绝不手写。排列和拓扑排序那边也有坑。康托展开时我一度忘了从0开始计数结果排名总是差1WA了三发。拓扑排序字典序最小那题我用了普通queue而不是priority_queue一直在跟“期望输出”对不上。这些坑都不是理解上的难全是细节上的虎写出来给后来人提个醒排序排列板块花最多时间的往往不是算法本身而是边界条件和比较器的细节校验。8. 写在后面这套东西到底该学到什么程度如果你刚开始学算法竞赛我的建议是先把STL sort用熟把归并排序求逆序对背下来然后用康托展开和next_permutation做几道全排列相关题目。到这一层你已经能应付大多数金牌线下赛事中排序相关的基础题。如果你想冲省一/国奖那就要在结构体自定义比较器、拓扑排序判环和字典序最小拓扑、以及排序配合分治/二分/双指针这些组合套路上多花时间。这个阶段做的题越多你会越发现排序本身不是考点排序背后的“有序性思维”才是。最后说一个我个人的体会排序和排列是所有算法板块里最适合“背模板 练套路”的一类但也是出错率最高的一类。出错的原因九成是细节不是不会。所以如果你正在备战一定要把比较器的严格弱序、稳定性、基准选择、康托展开的0/1计数、拓扑排序的判环条件这几个点单独拎出来多默写几遍。等你在考场上能条件反射地注意这些细节排序和排列这一块就算真正过关了。