#cspjc5. sort 排序函数专项

sort 排序函数专项

sort 排序专项

  • 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:: 前缀

  • 自定义比较函数(单级排序)

    对整数数组实现降序排序(从大到小)。

    bool cmp(int a, int b) {
        return a > b;  // 降序
    }
    sort(a, a + n, cmp);
    

2.关于自定义比较函数 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 表达式:一个“临时写的、没有名字的、用完就扔”的迷你函数。


  • 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>());     // 升序(与默认等价)

3.关于 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>()的情况下,指定结构体需要比较的成员变量的方法。


  • 多级排序(总分相同按学号)—— 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);

4.关于多级排序,以下说法正确的有( )?{{ 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 之间可以直接用 >、<、== 比较,比较规则是“字典序”(先比第一个元素,如果相等,再比第二个元素,依次类推)。

​ 字典序:“逐位比大小,比出结果就停,全比完了就比谁更短”。