C++知识点总结(16)：结构体排序

课程大纲

• 一、常见排序方法
• • 1. 桶排序
  • 2. 冒泡排序
  • 3. 选择排序
  • 4. 插入排序
• 二、结构体排序
• • 1. 融入实际
  • 2. 认识结构体
  • • 2.1 概念
    • 2.2 框架
    • • 2.2.1 存储
      • 2.2.2 输入输出
      • 2.2.3 结构体数组
      • 2.2.4 例题
      • • 2.2.4.1 结构体读写
        • 2.2.4.2 结构体交换
• 三、sort函数
• • 1. 使用方法
  • 2. 固定格式
• 四、结构体和sort函数
• • 1. 成绩排名
  • 2. NOIP 09年真题 洛谷P1068

一、常见排序方法

我们以下面的序列为例，看一看桶排序、冒泡排序、选择排序、插入排序的排序过程。
$$<5,2,7,1,4>$$

1. 桶排序

借助 cnt[] 数组的下标进行存储，适用于正整数和集中数字的排序。

2. 冒泡排序

两两元素比较，每一轮找出最大数字冒到最后一个位置。

3. 选择排序

找最小值和区间的第一个元素交换。

4. 插入排序

重复插入元素（扑克牌）。

二、结构体排序

1. 融入实际

如果按照原来的思想，需要进行 $5$ 个数组，更占空间。

2. 认识结构体

2.1 概念

用户自定义一个数据类型，可以包含很多基础数据类型。

2.2 框架

2.2.1 存储

struct Node // 结构体类型名后不带(){char name[105]; // string类型最好用char[]数组，string可能导致不稳定int gold; // 数据类型 + 名称int silver;int copper;int sum;}score; // 一定记得加分号Node score = {"ml", 6, 5, 8, 19}; // 存储数据

2.2.2 输入输出

cin >> score.name >> score.gold >> ...;cout << score.gold; // 输出金牌数

2.2.3 结构体数组

Node nodes[105];

这样可以让一组数据实现交换。

swap(nodes[1], nodes[3]);

或者一个数据。

swap(nodes[1].gold, nodes[3].gold);

2.2.4 例题

2.2.4.1 结构体读写

要求：第一行输入n，接下来n行输入一个名字+一个年龄，要求输出对应名字和对应的

#include using namespace std;int n;struct Node{char name[55];int age;}people;int main(){cin >> n;for (int i = 1; i <= n; i++){cin >> people.name >> people.age;cout << people.name << "年龄为" << people.age << endl;}return 0;}

运行结果：

[IN]2Andy 15Anne 14[OUT]Andy年龄为15Anne年龄为14

2.2.4.2 结构体交换

要求：第一行输入n表示人数，k和m表示对应需要交换的数组下标。

#include using namespace std;int n, k, m;struct Node{char chn[1005];char eng[1005];int grade;double high;}stu[1005];int main(){cin >> n >> k >> m;for (int i = 1; i <= n; i++){cin >> stu[i].chn >> stu[i].eng >> stu[i].grade >> stu[i].high;}swap(stu[k], stu[m]);for (int i = 1; i <= n; i++){cout << stu[i].chn << " " << stu[i].eng << " " << stu[i].grade << " " << stu[i].high << endl;}return 0;}

三、sort函数

1. 使用方法

#include #include  // 必须导入算法头文件using namespace std;int main(){int a[10] = {10, 9, 8, 3, 4, 5, 7, 2, 6, 1};sort(a+2, a+8);for (int i = 0; i <= 9; i++){cout << a[i] << " ";}return 0;}

sort() 函数中，第一个参数 + 的是多少就是起始排序的下标；第二个参数 + 的是多少就是种植排序的下标 $-1$ 。sort() 默认会进行升序排序，要使用降序排序，则应该使用：

// 方法1: 运用某些朝纲的东西sort(a, a+5, greater<int>());// 方法2: 自己定义比较规则bool cmp(int a, int b){return a > b; // 降序// return a < b; 升序}sort(a, a+5, cmp);

2. 固定格式

使用前需要添加头文件：

#include 

使用格式：

sort(数组 + 起始下标, 数组 + 终止下标 + 1)

四、结构体和sort函数

1. 成绩排名

题目描述
综合测评结束啦，现在语文数学成绩都出来了。我们再来排个序，排序规则如下：
语文成绩高的排在前面；
如果语文成绩一样，数学成绩高的排前面；
如果语文成绩和数学成绩都一样，按学号从小到大排序。
请你写代码输出一下排序结果吧
输入描述

输入有 n + 1 行，第一行是一个整数 n (0 < n < 30)，为学生总人数；
接下来的 n 行中，每一行有三个整数，分别为学号 id（0 < id < 100），语文成绩 ch (0 < ch <= 100)，数学成绩 ma（0 < ma <= 100），每个人的学号一定不同

输出描述

输出有 n 行，每行有学号、语文成绩和数学成绩，用空格隔开，按题目要求排序

样例1
输入

218 90 9512 90 95

输出

12 90 9518 90 95

样例2
输入

310 90 9524 99 6034 90 97

输出

24 99 6034 90 9710 90 95

【参考程序】

#include #include using namespace std;int n;struct Node{int id, chn, mth;}stu[35];bool cmp(Node a, Node b){if (a.chn != b.chn){return a.chn > b.chn;}else if (a.mth != b.mth){return a.mth > b.mth;}else{return a.id < b.id;}}int main(){cin >> n;for (int i = 1; i <= n; i++){cin >> stu[i].id >> stu[i].chn >> stu[i].mth;}sort(stu+1, stu+n+1, cmp);for (int i = 1; i <= n; i++){cout << stu[i].id << " " << stu[i].chn << " " << stu[i].mth << endl;}return 0;}

我们在书写 cmp() 函数的时候，传入的参数可能是 int 类型或者我们自定义的 Node 类型。int 类型可以调换一维数组的元素，Node 类型可以调换二维数组的一维数组。

2. NOIP 09年真题 洛谷P1068

问题描述

世博会志愿者的选拔工作正在A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m*150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

第一行，两个整数n，m（5 ≤ n ≤ 5000，3 ≤ m ≤ n），中间用一个空格隔开，其中n 表示报名参加笔试的选手总数，m 表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。第二行到第n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k（1000 ≤ k ≤ 9999）和该选手的笔试成绩s（1 ≤ s ≤ 100）。数据保证选手的报名号各不相同。

输出格式

第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例1
输入

6 31000 903239 882390 957231 841005 951001 88

输出

88 51005 952390 951000 901001 883239 88

提示
样例说明： $m\ast 150％=3\ast 150％=4.5$ ，向下取整后为 $4$ 。保证 $4$ 个人进入面试的分数线为 $88$ ，但因为 $88$ 有重分，所以所有成绩大于等于 $88$ 的选手都可以进入面试，故最终有 $5$ 个人进入面试。
【参考代码】

#include #include using namespace std;int n, m, line, people;struct Node{int id, s; }ps[5005];bool cmp(Node a, Node b){if (a.s != b.s){return a.s > b.s;}return a.id < b.id;}int main(){cin >> n >> m;for (int i = 1; i <= n; i++){cin >> ps[i].id >> ps[i].s;}sort(ps+1, ps+n+1, cmp);people = (int)(m * 1.5);line = ps[people].s;while (ps[people+1].s == line){people++;}cout << line << " " << people << endl;for (int i = 1; i <= people; i++){cout << ps[i].id << " " << ps[i].s << endl;}return 0;}