算法竞赛里排序是真正的地基。无论是数据预处理、贪心策略的先后顺序、二分答案的可行性检查还是排列组合计数几乎都建立在“有序”两个字之上。但这个系列写到第八篇我特别想把“排序”和“排列”放在一起讲——因为在赛场上它们经常被当成两个孤立的知识点实际上是一套组合拳排序决定“顺序”排列决定“顺序的枚举方式”两者配合才能解决很多看起来无从下手的题目。我见过太多选手在熟练背诵快排代码之后反而被一个“多次升序排序”的简单题卡住也见过有人天天用next_permutation却不知道排列和排序之间的那道桥是康托展开。这篇就把赛场上真正有价值的用法串一遍从选择排序的循环不变量证明到归并排序顺手数逆序对再到结构体cmp的隐藏坑最后聊排列生成与编号。1. O(n²)排序在竞赛里还有没有活路选择排序与循环不变量1.1 热身为什么出题人还要我们手写排序先问一个很实际的问题既然std::sort两行就搞定了为什么算法竞赛里还会出现“请写出选择排序”“请证明冒泡排序正确性”这种题因为排序算法是少数“代码极短但思想极深”的题材。出题人想考的不是你能不能写出sort而是你是否理解“有序性”是怎么一步步建立起来的。更关键的是循环不变量这个思维工具不只是为证明排序服务的——二分查找、KMP的next数组、单调栈全都依赖同一种证明逻辑。热词里有人专门搜索“clrs 选择排序循环不变量证明”说明这确实是被反复问过的基础题。想在竞赛里稳定拿分至少要能手写三类 O(n²) 排序选择、冒泡、插入。这三兄弟里选择排序的代码最直观循环不变量最好讲。1.2 用循环不变量证明选择排序选择排序的思路一句话每一轮从未排序部分挑出最小值放到已排序部分的末尾。伪代码如下for i 0 to n-2: min_index i for j i1 to n-1: if a[j] a[min_index]: min_index j swap(a[i], a[min_index])给出严格的循环不变量分三步证明初始化循环开始前i 0已排序部分a[0..i-1]是空集空集天然“有序且所有元素都不大于未排序部分”不变量成立。保持假设第i轮开始时不变量成立即a[0..i-1]已经排好序且其中每个元素都不大于a[i..n-1]中的任意元素。内层循环在未排序部分里找到最小值a[min_index]把它和a[i]交换。交换后a[i]是原未排序部分的最小值它一定大于等于a[i-1]这是保持条件给的又小于等于a[i1..]中所有元素。于是a[0..i]有序且所有元素不大于a[i1..]不变量保持。终止循环结束时i n-1此时a[0..n-2]有序且不大于a[n-1]于是整个数组有序。这个证明写出一次就不会再忘了。它还有一个附加价值让你明白“任何一次交换都不会破坏前面已经有序的部分”这是很多排序题优化的指导思想。1.3 冒泡和插入排序小规模与“近乎有序”的救场选择排序虽然简单但在竞赛里的实用地位最差——它的操作次数和逆序对无关永远做满n(n-1)/2次比较而且不稳定。真正在特定场景能救场的是插入排序。它处理“近乎有序”的数据非常快如果数组已经有序内层循环一查就空时间复杂度退化成 O(n)。很多选手写快排时遇到近乎有序的大数据被卡成TLE临时手写插入排序做小规模兜底是常用招数。冒泡排序在竞赛里几乎只出现在两类场合一是在“交换相邻元素求最少交换次数”的问题里当思维模型因为每次交换相邻元素恰好消去一个逆序对二是作为“最多 k 轮冒泡后数组长什么样”的模拟题。我建议你把插入排序的代码练到闭眼能写因为sort的常数太大时对小规模区间直接插入排序往往能跑到快排的两倍速度。比如我手写的快排里if (r - l 16)就会切到插入排序这个阈值在比赛里反复用都稳。2. 快排与归并的竞赛定位逆序对这个隐藏收益2.1 快排在竞赛里的退化场景与工程兜底快排在平均情况下是 O(n log n)但比赛最怕的就是“平均情况”四个字。当你面对的数据是升序、降序、完全相同的数组裸快排每次分割都极度不平衡递归深度变成 O(n)直接爆栈。工程上的标准解是introsort先正常快排当递归深度超过2 * log2(n)时改用堆排序。但竞赛里追求简洁常见做法是随机选pivot把mid拿出来交换到首尾再分割或者使用三数取中取l、mid、r三个位置的中间值当pivot。随机化不只是为了“运气”它的本质是把最坏情况从“固定输入让你卡死”变成“概率几乎为零”。出题人构造数据时假定你用的是固定pivot一旦随机卡你的数据就失效了。2.2 归并排序稳定、可求逆序对归并排序在竞赛中的出场率远高于它在工程中的地位核心原因是它有快排没有的两样东西稳定相等的元素保持原有相对顺序可以边排序边统计逆序对。逆序对的定义是i j且a[i] a[j]的数对数量。在二路归并的合并阶段两个有序子数组合并时如果从右侧数组取一个元素放进结果说明左侧数组剩余的所有元素都大于它因此每一次“取右侧”都要累加左侧剩余数量long long merge_sort(int l, int r) { if (l r) return 0; int mid (l r) 1; long long ans merge_sort(l, mid) merge_sort(mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (a[i] a[j]) tmp[k] a[i]; else { tmp[k] a[j]; ans mid - i 1; } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) a[p] tmp[p]; return ans; }注意一个细节当a[i] a[j]时我们取左侧这样相等元素不会被计入逆序对统计的就是严格大于关系。如果你想要“大于等于”的逆序对只需要把条件改成a[i] a[j]。这个区别在题目里很容易踩坑读题时一定要看清。2.3 什么时候选谁复杂度、常数与额外空间竞赛选手经常忽略常数问题。一个O(n log n)算法被写成常数爆炸的版本可能比 O(n²) 还慢。算法平均时间最坏时间额外空间稳定性常数快速排序O(n log n)O(n²)O(log n)不稳定小归并排序O(n log n)O(n log n)O(n)稳定中堆排序O(n log n)O(n log n)O(1)不稳定较大我的建议很直接比赛默认用std::sort但当要求手写时优先写归并。因为手写快排很容易在小细节上写错导致退化而归并的实现模式固定、不容易犯致命错误还能顺手处理逆序对。如果空间卡得很死再考虑堆排序。3. sort()背后的规则比较器写法与稳定性的工程细节3.1 各语言排序函数的底层差异很多选手在 C 里用std::sort在 Java 里用Arrays.sort在 Python 里用sorted以为它们“都一样”。实际上差别很大而且这些差别会直接体现在 WA 和 TLE 上。C 的std::sort是 introsort不稳定。这意味着两个相等的元素排序后相对位置不保证。如果你对一组(id, score)排序希望同分的保持输入顺序就必须用std::stable_sort它内部是归并排序稳定但会多占 O(n) 空间。Java 的Arrays.sort更隐蔽对int[]这类基本类型用 Dual-Pivot Quicksort不稳定对对象数组用 TimSort稳定的。如果你把Integer[]和int[]混着用结果可能都不一样。Python 的sorted和list.sort()用的都是 TimSort稳定。但 Python 的排序是解释执行的常数是 C 的几十倍甚至上百倍数据量一大就必须小心。我写过n 10^6的题目Python 的sort勉强能撑住但如果排序在循环里做多次基本没戏。3.2 结构体排序与 cmp 的正确姿势热词里那个“结构体排序cmp真题”我印象很深因为每年都有人栽在同一个地方cmp写得过于随意。竞赛里最常见的错误是“只写大于不写等于”比如bool cmp(const Node x, const Node y) { if (x.score ! y.score) return x.score y.score; return x.id y.id; }这个写法是对的先按分数降序分数相同按 id 升序。关键点是对于任意两个元素如果二者等价返回值必须恒为 false。也就是说如果cmp(x, y)为 true那么cmp(y, x)必须为 false如果cmp(x, y)和cmp(y, x)都为 false则二者等价等价关系必须传递x等价于y且y等价于z则x必须等价于z。这组规则叫“严格弱序”。很多选手贪省事写成return x.score y.score;当两个分数相等时cmp(x, y) false且cmp(y, x) false等价成立排序还能跑。但一旦加上了不规范的比如return x.score y.score;就可能出现不等价却无法成环的问题导致未定义行为。用 C 排序时比较器里永远用或不要用或这是死规矩。C 里除了写函数外更推荐用 lambdasort(v.begin(), v.end(), [](const Node x, const Node y) { if (x.score ! y.score) return x.score y.score; return x.id y.id; });lambda 的好处是结构体字段多的时候不用来回跳着看函数定义代码可读性高很多。3.3 稳定性陷阱与多关键字的排序顺序多关键字排序有个经典技巧先按次要关键字排序再按主要关键字排序前提是第二次排序不能破坏第一次的小顺序也就是要求稳定排序。举个例子按成绩降序再按学号升序。正确做法是先按学号升序排好再用稳定排序按成绩降序。因为稳定排序会保留之前学号的相对顺序于是成绩相同时学号自然升序。如果用std::sort这种不稳定的靠“先次要后主要”就行不通必须老老实实写完整cmp。竞赛里我建议一步到位在cmp里把多级比较全部写完不依赖稳定性减少心智负担。热词里还有“外号表头排序”——我理解是在实现表格点击列头排序的需求。这类鼠标点击交互里用户往往要求“点第一列升序再点第二列时如果值相等还要维持上一列的顺序”这种场景工程上就会用到稳定排序。竞赛题不会考界面交互但考的是同一思想稳定性的本质是对已有有序信息的尊重。理解了这个很多题都通。4. 排序的花式应用字符串、多次升序与统计型排序4.1 字符串排序的三层需求字符串排序是搜索引擎里常年高频的热词它也算“排序”题的一种。竞赛里的字符串排序通常有三层第一层直接按字典序排整个字符串std::sort对string类型天然支持operator一行搞定。第二层按字符串长度排序长度相同再按字典序。这类题一般用结构体存len和s然后自定义cmp。第三层才是真正的坑比如“对字符串按后缀排序”——这是后缀数组的领域属于中级算法不展开说但它的前置思想是两个字符串比较可以拆成多个关键字的比较这其实就是基数排序的思路。我实际做题的体会是字符串排序题 90% 卡在cmp上而不是卡在算法上。下回看到字符串排序先冷静确认“按什么关键字、是否多级、是否稳定”再动手写代码。4.2 “多次升序排序”题目的本质热搜词里出现了一个很典型的题面“小杨有一个包含 n 个正整数的序列 a。小杨计划对序列进行多次升序排序。”这类题竞赛里很常见看起来像是在整人实际上考的是幂等性。两个升序排序连续做效果等同于只做一次。所以如果题里说“对整个序列进行多次升序排序”答案基本就是排一次。但更狡猾的版本是区间多次升序排序。比如给定若干操作每个操作把[l, r]升序排序所有操作做完后问某个位置的值是多少。这种题第一次见会懵但稍微想一下就明白如果两个排序区间重叠并且第一个排完后区间内已经有序第二个排序的效果会被削弱甚至消失。处理思路有几种n 很小时直接模拟每个排序操作复杂度 O(m * n log n)能过就能过n 很大、操作很多时需要对区间排序做离线处理典型方案是把排序操作看成赋值操作用线段树或并查集跳过去如果多次排序覆盖整个序列答案就是排一次。我之前在个人赛里遇到过一次题目伪装成“小杨对序列不停排序求第 k 个数”直接把题读穿3分钟写出sort(a, an)全场最快。这种题本质不是让你排序而是让你识别排序的多余性。4.3 排序统计与计数排序的偷鸡技巧“排序统计”这个热词在竞赛里对应的是另一类问题不只求有序序列还要统计频次、中位数、前 K 大。如果值域有限比如所有数都在[0, 10^6]以内计数排序是比赛里的超级大招。它的时间复杂度是 O(n V)这里的 V 是值域。对 n 10^5、值域 10^6 的数据跑得飞快而且天然稳定完全不需要cmp。// 只统计不下钻手写快 int cnt[MAXV]; for (int i 0; i n; i) cnt[a[i]]; for (int v 1; v maxA; v) { while (cnt[v]--) cout v ; }这类代码在“正整数排序”的热搜里反复出现是有原因的当题目只要求排序且值域有限时别写快排直接开桶。一组数据 10^5 个元素值域 10^5开桶排序比sort快两到三倍而且绝对不爆栈。还有一个更隐蔽的技巧求第 K 大或中位数时不一定要排完整。nth_elementC 的std::nth_element可以做到平均 O(n) 找到第 K 大但它是部分排序只保证第 K 个元素就位左侧都小于等于它、右侧都大于等于它。用它的场景是“你只关心一个位置不关心全局顺序”。5. 排列的生成与康托展开给每个全排列编号5.1 next_permutation 的正确打开方式排列是“排序”的近亲。竞赛里最常见的排列操作是枚举全排列C 选手直接用next_permutationvectorint p {1, 2, 3}; do { // 处理当前排列 } while (next_permutation(p.begin(), p.end()));这个函数会原地把p变成字典序下一个排列如果已经是最后一个它会返回false并把p变成字典序最小的排列。注意两个坑必须从有序序列开始枚举否则会漏掉前面的一部分排列总排列数是 n!n10 是 362 万枚举可以接受n12 是 4.79 亿完全不现实。所以用next_permutation前先算算 n! 的数量级。如果要求“上一个排列”C 里对应的是prev_permutation但竞赛题很少用它通常字典序方向从前往后就够了。5.2 康托展开把排列映射成一个自然数很多状态压缩动态规划题里你手里的状态是一个长度很短的排列。如果直接存排列本身状态空间很大且没法用数组索引如果给排列编一个号就能压缩到一维数组。康托展开就是给定排列p[1..n]它的序号0-based等于X sum( a[i] * (n - i)! )其中a[i]表示“从第 i 位起后面还有多少个比p[i]小的数字”。举个例子排列{3, 2, 1}i0数字 3后面比 3 小的有 2 个贡献 2 * 2! 4i1数字 2后面比 2 小的有 1 个贡献 1 * 1! 1i2数字 1后面比 1 小的有 0 个贡献 0 * 0! 0合计 X 5。也就是说在 n3 的排列里按字典序从 0 开始数{3,2,1}排在第 5 位0-based 是 51-based 是 6即它是最后一个。实现时用树状数组或线段树维护“没用过的数字”里有多少个小于当前值复杂度 O(n log n)。// 树状数组维护剩余数字集合 long long cantor(vectorint p, int n) { Fenwick bit(n); long long X 0; long long fact 1; for (int i n - 1; i 1; i--) fact * i; // (n-1)! for (int i 0; i n; i) { int smaller bit.query(p[i] - 1); // 比p[i]小且未使用的个数 X smaller * fact; bit.add(p[i], 1); if (n - 1 - i 0) fact / (n - 1 - i); } return X; }实际写时阶乘可以用递推预处理好避免每次都算。5.3 逆康托展开由编号还原排列逆康托展开是编码的逆过程。给定编号 X还原出排列先维护有序集合{1, 2, ..., n}从高位到低位对i 0..n-1把 X 除以(n-i-1)!商就是“还有几个更小的数”也就是要挑选集合里第商1个元素取出该元素X 对阶乘取余继续下一轮。这个操作在“求第 K 个字典序排列”的题目里是标准答案。比如 n9、K10^5直接循环 n! 枚举是不现实的但逆康托展开一次 O(n²) 搞定。竞赛里的排列题往往在 n ≤ 8 时直接枚举n ≤ 12 时考虑状态压缩 DPn ≤ 20 的排列题目基本要借助康托展开把排列压缩成整数做状态。知道这个路线一看到数据范围就能确定解法方向。5.4 排列状态的优化排序与排列的组合拳最后把“排序”和“排列”真正串起来说一个常见题型你有一个数组希望通过排序配对、贪心选择使得某个排列的代价最小。典型例子是“安排任务顺序”或“匹配两个数组”。通常思路是先排序数组再研究排列的规律。排序能让“比较大小”变成 O(1) 的查表操作而排列负责“顺序方案”。比如求“两个数组配对的最大乘积”排序后一个升序一个降序相乘即可而类似“旅行商问题”这种顺序相关的问题就只能枚举排列或状态压缩 DP。排序把无序变有序排列把有序变可枚举组合起来就是完整的解题链路。我写过一道比赛题给了 n 个物品和 m 个槽位每个槽位有不同的收益系数要求分配方案最大化总收益——排序后贪心直接做原理就是“收益系数大的槽位配价值大的物品”这一步不是排列题但它把所有可能的排列方案一次压缩成线性选择这就是排序的威力。个人经验比赛里关于排序和排列的三条建议第一能用库函数绝不自写。手写快排在竞赛里唯一的意义是应付考手写题和展现理论功底实际比赛数据量大、时间紧std::sort经过高度优化比多数选手手写的版本都快。而stable_sort、nth_element、partial_sort这种库函数很多选手不知道白白丢分。第二一定要练熟逆康托展开和归并排序求逆序对。这两个点覆盖面极广一个是排列问题通向状态压缩的关键一个是排序问题通向计数问题的钥匙。每次比赛前我会把这俩默写一遍五分钟保底考场不慌。第三读题时先看数据范围再定排序策略。值域小就考虑计数排序n 小就考虑直接冒泡n 很大但有多次排序操作就先想操作能不能合并这比背一堆模板更重要。排序思想的核心从来不是把数字排整齐而是把混乱的信息整理成可以利用的结构——理解了这一点排序和排列就不再是两个知识点而是同一把刀的两面刃。