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

一、常见排序方法

我们以下面的序列为例，看一看桶排序、冒泡排序、选择排序、插入排序的排序过程。
$$<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 <iostream>
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]
2
Andy 15
Anne 14

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

2.2.4.2 结构体交换

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

#include <iostream>
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 <iostream>
#include <algorithm> // 必须导入算法头文件
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 <algorithm>

使用格式：

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
输入

2
18 90 95
12 90 95

输出

12 90 95
18 90 95

样例2
输入

3
10 90 95
24 99 60
34 90 97

输出

24 99 60
34 90 97
10 90 95

【参考程序】

#include <iostream>
#include <algorithm>
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 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88

输出

88 5
1005 95
2390 95
1000 90
1001 88
3239 88

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

#include <iostream>
#include <algorithm>
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;
}