从手写 Sort 到 tuple：一次多条件排序的学习复盘

一道 NOIP 普及组 T1，被我写成了两轮排序，外加一段同分区间扫描。

代码还没报错，我先看心虚了。

这次做的是洛谷 P1093 奖学金。题目只要求给学生排个名：总分高的在前；总分相同看语文；语文也相同，学号小的在前。最后输出前五名。

三条规则摆在那里，我最初的想法也很直白：既然规则分三层，那就分层排序。

先按总分排序；
找出总分相同的区间；
在区间里按语文排序；
如果语文还相同，再处理学号。

为了少复制几段代码，我还写了一个 Sort(p, q, S)：S == "Sum" 时排总分，S == "Chi" 时排语文。现在看，这个方向不是毫无道理，只是有点像为了整理三支笔，先做了一只带分区、滑轨和密码锁的笔盒。

第一版：我其实手写了一个选择排序
#

核心代码是这样的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void Sort ( int p , int q , string S ) {
    for ( int i = p ; i <= q ; i++ ) {
        if ( S == "Sum" ) {
            int tmp = a[i].Sum ;
            int tmp_range = i ;

            for ( int j = p + 1 ; j <= q ; j++ ) {
                if ( a[j].Sum > tmp ) {
                    tmp = a[j].Sum ;
                    tmp_range = j ;
                }
            }

            swap(a[i] , a[tmp_range]) ;
        }
    }
}

它每一轮从剩余学生里找最高分，再把那个人交换到当前位置，本质上就是选择排序。

问题藏在内层循环：

1
for ( int j = p + 1 ; j <= q ; j++ )

当外层已经走到 i = p + 2，前面的元素属于“已排序区”，却又被拉回候选名单。前脚刚排好，后脚又参加海选，队伍当然可能被重新搅乱。搜索应该从 i + 1 开始：

1
for ( int j = i + 1 ; j <= q ; j++ )

如果还不熟悉选择排序，可以先看博客园的《数据结构与算法——选择排序》。它把“已排序区怎样一点点扩大”和比较次数 n(n-1)/2 都展开了；读完再回来看这里的 p + 1，会更容易明白这不是普通的下标手滑，而是搜索区间的定义错了。

同分区间还有一个不太显眼的边界：

1
2
3
4
5
6
7
8
int tmp_q = i ;

for ( int j = i + 1 ; j <= n ; j++ ) {
    if ( a[j].Sum != a[i].Sum ) {
        tmp_q = j - 1 ;
        break ;
    }
}

如果一群同分学生刚好站到数组末尾，循环始终遇不到“不同总分”，tmp_q 就一直等于 i。他们都挤到队尾了，程序反而假装没看见。

更合适的初值是：

1
int tmp_q = n ;

先假设同分区间延伸到末尾，中途找到不同分数，再把右端缩到 j - 1。

此外，我的第二轮只按语文排序，还没有补上“语文相同时学号小的优先”；程序中又保留了两遍前五名和空行。前者让顺序出错，后者即使名次正确，也会因为输出格式不符而 WA。调试输出忘删这件事没什么技术含量，杀伤力倒一直很稳定。

原来的方法能不能修？能，只是补丁开始排队了
#

继续沿着原思路，手写排序可以改成：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void Sort ( int p , int q , string mode ) {
    for ( int i = p ; i < q ; i++ ) {
        int pos = i ;

        for ( int j = i + 1 ; j <= q ; j++ ) {
            if ( mode == "Sum" && a[j].Sum > a[pos].Sum ) {
                pos = j ;
            }
            else if ( mode == "Chi" &&
                     ( a[j].Chi > a[pos].Chi ||
                       ( a[j].Chi == a[pos].Chi && a[j].X < a[pos].X ) ) ) {
                pos = j ;
            }
        }

        swap(a[i] , a[pos]) ;
    }
}

然后主程序还要保留“先排总分—扫描同分区间—再排语文”的流程。

第一次选择排序需要平方级比较；最坏情况下所有学生总分都相同，同分区间又完整排一次。因此整体时间复杂度仍是 O(n^2)。学生数组占 O(n) 存储，排序本身只使用几个临时变量，辅助空间是 O(1)。

本题 n <= 300，O(n^2) 不一定跑不动。真正让我不舒服的是，三条排名规则被拆散在不同位置：字符串可能拼错，区间可能漏尾巴，再加一条规则就再加一层补丁。能过和好维护，并不是一回事。

换一个问题问：两个人谁在前？
#

我原来一直在问：“怎样先排总分，再处理同分？”

std::sort 的比较器问的是：

随便拿出两个学生 x 和 y，x 是否应该排在 y 前面？

比较器像一个只管两个人的裁判。它不用亲手排完整支队伍，只要每次都给出一致的先后关系，sort 会负责其余工作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
bool cmp ( const node& x , const node& y ) {
    if ( x.Sum != y.Sum ) {
        return x.Sum > y.Sum ;
    }

    if ( x.Chi != y.Chi ) {
        return x.Chi > y.Chi ;
    }

    return x.X < y.X ;
}

调用只剩一次：

1
sort(a + 1 , a + n + 1 , cmp) ;

这里是左闭右开区间 [first, last)，所以 a + n + 1 指向 a[n] 后面，而不是多排了一个元素。

如果对“第三个参数到底是什么”仍有点模糊，可以接着看博客园的《C++——sort 与比较器》。它先拆三个参数，再分别给出普通函数、函数对象和 operator< 的写法，很适合用来建立第一张 sort 语法地图。腾讯云上的《〈C++ Primer〉第 10 章：泛型算法》笔记则把比较器放回“谓词”和泛型算法的大背景里；只读“定制操作”一节，就能知道这套思路不只服务于排序。

比较器的返回值也值得单独说一句：

1
cmp(x , y) == true

它表示“按照我定义的规则，x 应排在 y 前面”，并不表示 sort 此刻一定执行一次交换。把它理解成先后关系，比猜标准库内部正在交换谁稳得多。

另外不能把降序写成：

1
return x.Sum >= y.Sum ;  // 错误

当 x 和 y 相等时，cmp(x, y) 与 cmp(y, x) 都会返回 true，等于裁判宣布两个人都必须站在对方前面。比较器需要满足严格弱序，至少要保证 cmp(x, x) 为 false，所以这里用 >，不用 >=。

这个坑如果只记一句“不能带等号”，过几天很容易忘。Codeforces 上的英文短文 Always use strict weak ordering in std::sort 只有一个错误示例和一个正确示例，展示了 <= 如何导致运行时错误；篇幅短，重点看两段代码和正文第一段即可。想把条件看完整，再查中文的 std::sort 参考页中 “Compare” 与复杂度部分。前者负责留下印象，后者负责把边界钉牢。

std::sort 的比较次数是 O(n log n)。输入的学生数组仍占 O(n) 空间；标准并没有要求所有实现采用同一种内部算法，常见实现还会使用大约 O(log n) 的递归栈。对这道题来说，速度提升不是最惊艳的部分，一次把三条规则写在同一个函数里才是。

Lambda：`sort` 后面为什么突然长了大括号
#

普通 cmp 已经足够清楚。但如果这条规则只用一次，也可以把它写在调用现场：

1
2
3
4
5
6
sort(a + 1 , a + n + 1 ,
     [] ( const node& x , const node& y ) {
         if ( x.Sum != y.Sum ) { return x.Sum > y.Sum ; }
         if ( x.Chi != y.Chi ) { return x.Chi > y.Chi ; }
         return x.X < y.X ;
     }) ;

第一次看这段，最扎眼的通常是 [] 和最后的 });。拆开就没那么神秘：

1
2
3
[ 捕获列表 ] ( 参数列表 ) {
    函数体
}

整个 Lambda 是 sort 的第三个参数。结尾处，} 结束 Lambda，) 结束 sort 调用，; 结束语句。三位各回各家，没有哪个括号是突然混进来的。

这道题只用参数 x、y，不需要外部局部变量，因此捕获列表为空：

1
2
3
4
5
[]          // 不捕获外部局部变量
[ limit ]   // 按值捕获 limit
[ &cnt ]    // 按引用捕获 cnt
[ = ]       // 按值捕获用到的外部变量
[ & ]       // 按引用捕获用到的外部变量

如果想先用中文把 Lambda 的整体语法走一遍，前面的《〈C++ Primer〉第 10 章：泛型算法》笔记从“谓词为什么不够用”自然过渡到捕获列表，和这里的学习顺序很接近。若还想真正分清“值捕获复制了什么、引用捕获又要求谁活得更久”，可以看 LearnCpp 的英文教程 Lambda captures；文章较长，但只读 “The capture clause” 到 “Capture by reference” 即可，它用搜索字符串和计数器两个小例子把 [x] 与 [&x] 的差别跑了出来。

参数使用 const node&：& 避免每次比较都复制整个学生结构体，const 防止比较器顺手修改成绩。排序裁判可以判断名次，不能现场给人改卷。

tuple：把三层 if 收成一叠判定牌
#

理解 Lambda 后，还可以继续把三个 if 收起来：

1
2
return make_tuple(-x.Sum , -x.Chi , x.X)
     < make_tuple(-y.Sum , -y.Chi , y.X) ;

先分清几个名字：tuple 是保存若干元素的类模板，make_tuple 是创建元组的函数，get 用下标取元素，tie 可以把若干左值绑成一个引用元组。

想先把这些基础操作摸一遍，博客园的《C++ 之元组 std::tuple 常见用法》从创建、get 一直写到 tie 和 ignore，例子基本可以单独复制运行。本文只借用元组的比较能力，不必一口气看到后面的递归遍历。

元组按字典序比较：先看第 0 项，相同才看第 1 项，再相同才看第 2 项。可以把它想成三张按顺序翻开的判定牌：

1
(-总分, -语文, 学号)

总分和语文前面为什么有负号？因为元组默认按小的在前，而：

1
2
279 -> -279
264 -> -264

-279 < -264，所以原来更高的 279 分会排在前面。学号本来就要求从小到大，不需要取反。本题成绩总分范围很小，取负不会有整数溢出问题；如果关键字可能等于整型最小值，就应改回显式比较，别为了短一行去踩溢出的坑。

std::tie 为什么也经常和比较运算符一起出现？英文个人博客 Using a tie in C++ 很短，只讲两件事：怎样用 tie 实现结构体的字典序比较，以及怎样解包返回值。它特别适合在这里读，因为示例几乎就是“把一串 if 交给 tuple”。如果准备继续了解 operator<，Fluent C++ 的 How to Define Comparison Operators by Default in C++ 会比较手写运算符、std::tie 与 C++20 默认比较；重点看开头到 std::tie 那一段，后面的 C++20 内容可以先当预告片。

最终的排序表达式是：

1
2
3
4
5
sort(a + 1 , a + n + 1 ,
     [] ( const node& x , const node& y ) {
         return make_tuple(-x.Sum , -x.Chi , x.X)
              < make_tuple(-y.Sum , -y.Chi , y.X) ;
     }) ;

每次元组比较最多检查三个整数，因此单次比较仍是 O(1)；整个排序仍为 O(n log n)。临时元组只占常数空间，不改变整体空间级别。

这段确实短，但短的前提是我能随时把它重新展开成三个 if。否则 (-Sum, -Chi, X) 只是一串看起来很厉害、下次自己也不敢改的符号。

几种写法摆在一起
#

写法	时间复杂度	辅助空间	适合什么时候
手写选择排序并扫描同分区间	`O(n^2)`	`O(1)`	练习排序原理，或数据极小且逻辑简单
`std::sort` + 普通 `cmp`	`O(n log n)`	常见实现约 `O(log n)` 栈空间	第一次写多条件排序，规则最容易读清
`std::sort` + Lambda	`O(n log n)`	同上	比较规则只在调用处使用一次
重载 `operator<`	`O(n log n)`	同上	结构体在程序中有稳定、唯一的默认顺序
Lambda + `tuple`	`O(n log n)`	同上，临时元组为 `O(1)`	关键字多且能自然转成同向字典序

这些方法都需要保存 n 名学生，所以输入本身占 O(n) 空间。表格中的“辅助空间”只计算排序额外使用的部分，没有把学生数组再算一遍。

最终代码
#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std ;

struct node {
    int X , Chi , Math , Eng , Sum ;
} ;

node a[305] ;

int main ( ) {

    int n ;
    cin >> n ;

    for ( int i = 1 ; i <= n ; i++ ) {
        cin >> a[i].Chi >> a[i].Math >> a[i].Eng ;
        a[i].X = i ;
        a[i].Sum = a[i].Chi + a[i].Math + a[i].Eng ;
    }

    sort(a + 1 , a + n + 1 ,
         [] ( const node& x , const node& y ) {
             return make_tuple(-x.Sum , -x.Chi , x.X)
                  < make_tuple(-y.Sum , -y.Chi , y.X) ;
         }) ;

    for ( int i = 1 ; i <= 5 ; i++ ) {
        cout << a[i].X << " " << a[i].Sum << endl ;
    }

    return 0 ;
}

读入是 O(n)，排序是 O(n log n)，因此总时间复杂度为 O(n log n)。学生数组占 O(n)；排序的额外空间取决于标准库实现，常见实现主要使用 O(log n) 栈空间。

回头再看这段路
#

这次不是一个醒目的 WA 把我按回代码里，而是代码越写越长，我才开始怀疑：题目真的需要我维护两套排序和一组区间吗？

后来我顺着几个问题往下问：现成的 sort 能不能排结构体？第三个参数到底在回答什么？Lambda 的方括号和大括号各管什么？三个 if 能不能继续收起来？

路线最后变成：

手写选择排序并分组
起点
先把规则拆开处理，也因此碰见了搜索区间、同分尾段和第三关键字三个具体问题。
用 cmp 说清两名学生的顺序
不再维护多轮排序，只回答一个稳定的问题：谁应该站在谁前面？
把一次性规则写成 Lambda
比较逻辑留在 `sort` 旁边，调用位置和规则不再分居两处。
用 tuple 整理多级关键字
现在
把总分、语文和学号排成一叠有顺序的判定牌。

第一版并没有白写。要不是自己踩过 p + 1、末尾同分区间和第三关键字这些坑，我第一次看到 tuple 版，大概只会想：好短，先抄了再说。

现在至少能把它拆开，也能再装回去。

留给以后复习
#

几句要记住的
#

sort(first, last, comp) 排序的是 [first, last)。
comp(x, y) 返回 true，表示 x 应排在 y 前面，而不是承诺立刻交换。
比较器必须形成严格弱序；相等元素双向比较都应返回 false。
Lambda 的骨架是 [捕获列表](参数列表) { 函数体 }。
tuple 按字典序从前往后比较，适合表达多级关键字。
取相反数可以把安全范围内的数值降序转成升序；可能溢出时应显式比较。
比较复杂度时，要区分输入存储与算法的辅助空间。

三段核心代码
#

普通 cmp：

1
2
3
4
5
bool cmp ( const node& x , const node& y ) {
    if ( x.Sum != y.Sum ) { return x.Sum > y.Sum ; }
    if ( x.Chi != y.Chi ) { return x.Chi > y.Chi ; }
    return x.X < y.X ;
}

Lambda：

1
2
3
4
5
6
sort(a + 1 , a + n + 1 ,
     [] ( const node& x , const node& y ) {
         if ( x.Sum != y.Sum ) { return x.Sum > y.Sum ; }
         if ( x.Chi != y.Chi ) { return x.Chi > y.Chi ; }
         return x.X < y.X ;
     }) ;

Lambda + tuple：

1
2
3
4
5
sort(a + 1 , a + n + 1 ,
     [] ( const node& x , const node& y ) {
         return make_tuple(-x.Sum , -x.Chi , x.X)
              < make_tuple(-y.Sum , -y.Chi , y.X) ;
     }) ;

自测
#

数组使用 a[1] ~ a[n] 时，为什么右端要传 a + n + 1？
为什么不能写 return x.Sum >= y.Sum;？
[]、[=] 和 [&] 分别表示什么？
make_tuple(-x.Sum, -x.Chi, x.X) 怎样对应三层规则？
如果规则改成“总分高优先、数学低优先、学号小优先”，元组应该怎样写？

查看参考答案

sort 的右端不参与排序，a + n + 1 正好位于 a[n] 后面。
两个相等元素互相比较都会返回 true，违反严格弱序中的非自反性。
[] 不捕获外部局部变量，[=] 默认按值捕获，[&] 默认按引用捕获。
元组依次比较总分、语文和学号；成绩取反实现降序，学号保持升序。
make_tuple(-x.Sum, x.Math, x.X)。

继续读
#

这次学习复盘，也是这个博客重新开始后留下的第一篇完整技术笔记。

博客，重新开始

2026-09-07·627 字·2 分钟

博客日志 Hugo 博客成长

初一的时候，我第一次搭建了自己的 WordPress 博客。那时我还没有成年，只能使用妈妈的腾讯云账号。购买域名、提交备案、等待审核，再一点点调整主题和插件，这些过程让我第一次感觉到：原来互联网上真的可以有一块属于自己的地方。

第一版：我其实手写了一个选择排序#

原来的方法能不能修？能，只是补丁开始排队了#

换一个问题问：两个人谁在前？#

Lambda：sort 后面为什么突然长了大括号#

tuple：把三层 if 收成一叠判定牌#

几种写法摆在一起#

最终代码#

回头再看这段路#

手写选择排序并分组

起点

用 cmp 说清两名学生的顺序

把一次性规则写成 Lambda

用 tuple 整理多级关键字

现在

留给以后复习#

几句要记住的#

三段核心代码#

自测#

继续读#