一、课上练习

编程练习

1. 选择排序：L2131
2. 冒泡排序：L2151
3. 身份证排序：L2181
4. 整数奇偶排序：L2182
5. 成绩排序：L2183

二、知识总结

✨ sort函数的核心思想

在 C++ 中，sort 函数可以用来对一组线性存储的数据进行排序。默认情况下，sort 会对数据进行从小到大排序；如果需要修改排序规则，可以通过添加自定义的 cmp 函数来实现。

使用 sort 函数需要添加 std 命名空间（或使用 using namespace std）。

对存储了 n 个数的数组 arr 排序的基本用法如下：

sort(arr, arr + n); // 从小到大排序
sort(arr, arr + n, cmp); // 使用cmp函数自定义排序规则

其中，sort 的前两个参数分别是排序范围的起始地址和结束地址（左闭右开区间），第三个参数为可选的自定义比较函数。

✨ cmp 函数

sort 函数自定义排序规则所用的 cmp 函数是一种接受两个参数并返回布尔值的函数。对于两个参数 a 和 b，如果 cmp(a, b) 返回 true，则认为 a 应该排在 b 前面。

下面是一个从大到小排序的 cmp 函数示例：

bool cmp(int a, int b) {
    return a > b;
}

当 a > b 时返回 true，表示较大的数排在前面，从而实现降序排列。通过编写不同的 cmp 函数，可以灵活地实现各种自定义排序规则，例如按绝对值排序、按结构体某个字段排序等。

✨ sort函数的执行示例

下面通过具体例子展示 sort 函数的使用过程。

例1：基本排序

输入数组：arr = [5, 2, 8, 1, 9, 3]，n = 6
调用：sort(arr, arr + 6);
排序后：arr = [1, 2, 3, 5, 8, 9]

例2：使用 cmp 函数实现从大到小排序

bool cmp(int a, int b) {
    return a > b;  // a > b 时 a 排前面，即降序
}

sort(arr, arr + 6, cmp);

排序前：arr = [5, 2, 8, 1, 9, 3]
排序后：arr = [9, 8, 5, 3, 2, 1]

例3：结构体排序——按成绩降序，成绩相同按姓名字典序升序

1struct Student {
2    string name;
3    int score;
4};
5
6bool cmp(Student a, Student b) {
7    if (a.score != b.score) {
8        return a.score > b.score;  // 成绩高的排前面
9    }
10    return a.name < b.name;  // 成绩相同，姓名字典序小的排前面
11}

排序前：[("Bob",90), ("Alice",95), ("Charlie",90), ("David",85)]
排序后：[("Alice",95), ("Bob",90), ("Charlie",90), ("David",85)]

Bob 和 Charlie 成绩相同，按姓名字典序排列，Bob 排在 Charlie 前面。

例4：对数组的一部分进行排序

数组：arr = [5, 2, 8, 1, 9, 3]
只对下标 1~4 排序：sort(arr + 1, arr + 5);
排序后：arr = [5, 1, 2, 8, 9, 3]

sort 的排序范围是左闭右开区间：arr + 1 是起始位置（包含），arr + 5 是结束位置（不包含），所以排序的是 arr[1] 到 arr[4]。

✨ sort函数的解题步骤

使用 sort 解决排序问题的一般步骤：

1. 分析排序规则：仔细阅读题目，确定需要按什么规则排序（升序/降序/多关键字）
2. 确定数据结构：如果需要多关键字排序，通常需要定义结构体来存储多个字段
3. 编写 cmp 函数：根据排序规则编写比较函数，注意 return true 表示第一个参数应该排在前面
4. 确定排序范围：确定 sort 的起始和结束地址，注意是左闭右开区间
5. 调用排序并输出：调用 sort 后按要求输出结果

多关键字排序的 cmp 编写模板：

1bool cmp(Type a, Type b) {
2    if (a.第一关键字 != b.第一关键字) {
3        return a.第一关键字 > b.第一关键字;  // 第一关键字降序
4    }
5    return a.第二关键字 < b.第二关键字;  // 第二关键字升序
6}

✨ sort函数的常见错误

1. cmp 函数中使用 >= 或 <=：cmp 函数在两个元素相等时必须返回 false，否则 sort 可能会出现死循环或程序崩溃。例如 return a >= b; 是错误的写法，应该用 return a > b;
2. 排序范围写错：sort(arr, arr + n) 排序的是 arr[0] 到 arr[n-1]，写成 sort(arr, arr + n - 1) 会漏掉最后一个元素
3. cmp 函数参数类型不匹配：cmp 函数的参数类型必须和数组元素类型一致，排序 int 数组时参数类型要是 int，排序结构体数组时参数类型要是结构体类型
4. 忘记处理相等情况：多关键字排序时，必须先判断当前关键字是否不等，不等时才按当前关键字排序，相等时才进入下一个关键字的比较
5. 结构体传参效率低：当结构体较大时，cmp 函数的参数建议使用 const Student &a 引用传递，避免不必要的拷贝

三、课后练习

编程练习

1. n个一位数能够组成的最大数: L2184
2. 允许并列的排名：L2185