结构体数组与sort排序

sort是C++中最常用的排序工具，配合结构体可以处理带多个字段的复杂数据排序。核心分为两部分：sort函数的基础用法，以及自定义结构体的排序规则编写。

一、sort 基础用法

sort 函数定义在 <algorithm> 头文件中，适用万能头，底层是快速排序实现，默认按升序排列。

1. 排序范围：两个参数控制区间

sort 的排序范围遵循左闭右开规则：

sort(起始地址, 结束地址);

起始地址：排序的第一个元素的地址
结束地址：排序的最后一个元素的下一个地址
实际排序区间：[起始地址, 结束地址)，包含起点，不包含终点

常见场景

下标从0开始的数组，排全部n个元素：数组名就是首地址，结束地址为 a + n
```
int a[100];
sort(a, a + n); // 排 a[0] ~ a[n-1]
```
下标从1开始的数组，排1~n：起始为 a+1，结束为 a + n + 1
```
int a[100];
sort(a + 1, a + n + 1); // 排 a[1] ~ a[n]
```

排指定区间 l~r：起始为 a+l，结束为 a + r + 1

sort(a + l, a + r + 1); // 只排第 l 到第 r 个元素

2. 默认排序与降序写法

对于 int、double、char 等基础数据类型，sort 默认按升序排列。
如果需要降序，传入第三个参数 greater<类型>() 即可：

// 升序（默认）
sort(a + 1, a + n + 1);
// 降序
sort(a + 1, a + n + 1, greater<int>());

二、结构体基础

结构体是自定义的复合数据类型，可以把多个不同类型的变量组合成一个整体，适合描述一个对象的多个属性，特别是多属性排序中非常重要，因为sort只能排一个数组，而如果多个属性排序，例如先按总分排，总分相等则看语文这种需求，如果总分、语文成绩等用多个数组分开存，就没办法统一sort排序。

1. 使用三步法

结构体的使用必须按顺序：定义类型 → 定义变量/数组 → 访问成员

第一步：定义结构体类型

用 struct 关键字定义，大括号内写成员变量，最后加分号。

// 定义一个名为 Student 的结构体类型
struct Student {
    int id;     // 学号
    int math;   // 数学成绩
    int chinese;// 语文成绩
    int total;  // 总分
};

此时 Student 就和 int 一样，是一个可以用来定义变量的数据类型。

第二步：定义结构体数组

Student stu[1005]; // 定义一个长度为1005的学生数组

也可以在定义结构体类型的同时直接定义数组：

struct Student {
    int id, math, chinese, total;
} stu[1005];

第三步：访问成员

通过 . 运算符访问结构体内部的成员：

stu[i].id = 1001;
stu[i].math = 95;
stu[i].total = stu[i].math + stu[i].chinese;

2. 输入输出示例

int n;
cin >> n;
for (int i = 1; i <= n; i++) {
    cin >> stu[i].id >> stu[i].math >> stu[i].chinese;
    stu[i].total = stu[i].math + stu[i].chinese;
}

三、结构体排序：自定义 cmp 函数

sort 默认不知道结构体按什么规则排序，因此必须编写比较函数 cmp，告诉 sort 两个元素谁在前谁在后。

1. cmp 函数规则

返回值：bool 类型
参数：两个参数，类型与排序的结构体完全一致
返回值含义：
- 返回 true：认为第一个参数应该排在第二个参数前面，不交换位置
- 返回 false：认为顺序不对，需要交换

2. 两种写法

写法一：判断式写法（易理解）

先判断顺序是否正确，手动返回 true/false。
比如按总分降序排列：

bool cmp(const Student &a, const Student &b) {
    if (a.total > b.total) {
        return true;  // a总分更高，a应该在前面，不交换
    } else {
        return false; // 顺序不对，需要交换
    }
}

写法二：表达式写法（简洁推荐）

直接返回比较表达式，表达式为真则返回true，否则返回false。
两种写法完全等价，推荐直接写表达式，简洁不易错。

bool cmp(const Student &a, const Student &b) {
    return a.total > b.total; // 总分降序
}

3. 多级排序

当第一关键字相等时，按第二关键字排序，以此类推。
示例：先按总分降序，总分相同按学号升序

bool cmp(const Student &a, const Student &b) {
    if (a.total != b.total) {
        return a.total > b.total; // 总分不同：总分高的在前
    } else {
        return a.id < b.id;       // 总分相同：学号小的在前
    }
}

逻辑：先比第一关键字，不相等就直接返回第一关键字的比较结果；相等再比较第二关键字。

四、完整模板：学生成绩排序

题目要求

有n个学生，每个学生有学号、数学成绩、语文成绩。按总分从高到低排序，总分相同则按学号从小到大排序，输出排序后的结果。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

// 1. 定义结构体类型，同时定义数组
struct Student {
    int id;
    int math;
    int chinese;
    int total;
} stu[N];

// 2. 自定义排序规则
bool cmp(const Student &a, const Student &b) {
    if (a.total != b.total) {
        return a.total > b.total; // 总分降序
    } else {
        return a.id < b.id;       // 学号升序
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> stu[i].id >> stu[i].math >> stu[i].chinese;
        stu[i].total = stu[i].math + stu[i].chinese;
    }
    
    // 3. 调用sort，传入cmp函数
    sort(stu + 1, stu + n + 1, cmp);
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << stu[i].id << " " << stu[i].total << endl;
    }
    
    return 0;
}

五、核心总结

sort区间：排 l~r 就写 sort(a+l, a+r+1)
基础类型降序：直接用 greater<类型>()
结构体三步：定义类型 → 定义数组 → . 访问成员
结构体排序：必须写cmp函数，返回true表示第一个参数排前面
多级排序：先比第一关键字，不等则返回，相等再比下一级

结构体 + sort