#cspjc5. sort 排序函数专项
sort 排序函数专项
sort 排序函数专项
1.sort 的基本用法与默认排序
对普通 int 数组升序排序。
int a[5] = {5, 2, 8, 1, 3};
sort(a, a + 5);
例1:关于 sort 的默认行为,下列说法正确的有?{{ multiselect(1) }}
- 默认按升序(从小到大)排列元素
- 默认比较方式是使用
<运算符,即a < b为真时a排在b前面 - 若数组元素是结构体且未重载
<运算符,直接调用sort(arr, arr+n)会编译报错 - 默认排序的时间复杂度稳定为
O(n log n)(严格说不稳定,但初赛通常这样认为) sort的头文件是<algorithm>,使用前需using namespace std;或加std::前缀
2.自定义比较函数(单级排序)
对整数数组实现降序排序(从大到小)。
bool cmp(int a, int b) {
return a > b; // 降序
}
sort(a, a + n, cmp);
例1:关于自定义比较函数 cmp,下列说法正确的有( )?{{ multiselect(2) }}
- 当
cmp(a, b)返回true时,表示a应该排在b的前面 cmp(a, b)必须满足严格弱排序(Strict Weak Ordering),即不能出现cmp(a,b)和cmp(b,a)同时为true的情况- 若
cmp写成return a >= b;(带等号),会导致排序结果不确定甚至崩溃(破坏了严格弱序) - 自定义比较函数可以定义为类的静态成员函数或全局函数
- 比较函数可以写成
lambda表达式:sort(a, a+n, [](int a, int b){ return a > b; });
提示: lambda 表达式:一个“临时写的、没有名字的、用完就扔”的迷你函数。
3.greater<>() 与 less<>() 的用法(重点)
利用标准库提供的函数对象快速排序。
#include <algorithm>
#include <functional> // 必须包含!
int a[5] = {3, 1, 4, 1, 5};
sort(a, a + 5, greater<int>()); // 降序
sort(a, a + 5, less<int>()); // 升序(与默认等价)
例1:关于 greater<T> 和 less<T>,下列说法正确的有( )?{{ multiselect(3) }}
sort(a, a+n, greater<int>())等价于sort(a, a+n, [](int x,int y){ return x > y; });,即降序排序less<int>()是sort的默认比较方式,不写第三个参数时默认就是它- 使用
greater<int>()必须包含头文件<functional> - 如果自定义结构体
Student,可以用greater<Student>()排序,前提是Student重载了operator> greater<>()(C++14 起)可以省略模板参数,自动推导类型
提示: 结构体重载 operator>:是一种在结构体排序使用greater<Student>()的情况下,指定结构体需要比较的成员变量的方法。
4.多级排序(总分相同按学号, CSP 最高频场景)
学生信息包括 score(总分)和 id(学号),要求总分从高到低,若总分相同则学号从小到大。
struct Student {
int id;
int score;
};
bool cmp(const Student &a, const Student &b) {
if (a.score != b.score)
return a.score > b.score; // 一级:总分高的排前面
return a.id < b.id; // 二级:总分相同,学号小的排前面
}
sort(students, students + n, cmp);
例1:关于多级排序,以下说法正确的有( )?{{ multiselect(4) }}
- 上述代码实现了总分降序、学号升序的排序
- 若把
return a.id < b.id改成return a.id > b.id,则总分相同学号降序 - 可以借助
std::tuple简化写法:return tie(a.score, b.id) > tie(b.score, a.id);(不推荐) - 比较函数中,一级判断必须写在二级判断之前,否则先比较学号会破坏主要排序逻辑
- 若
score相同且id也相同,cmp返回false,这符合严格弱排序要求
提示: tuple(元组):可以把它想象成一个“万能小包裹”,里面可以装不同类型的数据。比如 tuple<int, int> 就是装了“两个整数”的包裹。std::tie:它的作用是创建这个包裹的“引用”,专门用来做比较或拆解数据,避免复制数据带来的性能损耗。 C++ 规定,两个 tuple 之间可以直接用 >、<、== 比较,比较规则是“字典序”(先比第一个元素,如果相等,再比第二个元素,依次类推)。 字典序:“逐位比大小,比出结果就停,全比完了就比谁更短”。