[C++知识库]算法基础(一)——C++排序sort()的用法

§ sort函数的使用

• 必须引入头文件algorithm
• 内部底层实现：由多种排序算法构成，根据数量级决定。大部分是快速排序，这是一个不稳定的排序
• 稳定排序：stable_sort()

基本用法和演示

1.对整个数组或数组中的一段进行排序

int num[105];
sort(num, num + 100);
//sort(起始位, 结束位的后一个位置)
sort(num + 4, num + 8);
//默认从小到大排序

其中有num[0]~num[99]一百个数，105是一般书写习惯，防止数组越界。

2.从大到小排序

sort(起始位, 结束位的后一个位置, 排序方法)

比较函数返回的是bool类型，函数参数中const建议写上，a在前b在后，a>b表示的是期望排在前面的元素的值大于排在后面的元素的值

3.自定义(如结构体)类型的排序

注：C++中没有结构体一说，只有类。

如果加条件：x项相等时

bool cmp(const node &a, const node &b) {
	if (a.x == b.x) {
		return a.y > b.y;
	}
	return a.x < b.x;
}

注：排序函数不能出现=或≥或≤，可能会出现死循环

排序函数也可以写在自定义类型里面，这样就不用传递第三个参数了(指定了一个默认的排序方法)：

struct node {
    int x, y;
    //函数后的const意思是不期待更改内部属性
    bool operator<(const node &b) const {
        if (this->x == b.x) {
            return this->y > b.y;
        }
        return this->x < b.x;
    }
};

§ 刷题

1.奖学金

样例输入

8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

样例输出

8 265
2 264
6 264
1 258
5 258

提交网址1

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
    int ch, ma, en, sum, id;
};

bool cmp(const node &a, const node &b) {
    if (a.sum == b.sum) {
        if (a.ch == b.ch) {
            return a.id < b.id;
        }
        return a.ch > b.ch;
    }
    return a.sum > b.sum;
}

int main() {
	//在本地编译器上的当前文件夹创建了input普通文件
	//从这个文件里读入输入数据
    //freopen("input", "r", stdin);
    node stu[305];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> stu[i].ch >> stu[i].ma >> stu[i].en;
        stu[i].id = i + 1;
        stu[i].sum = stu[i].ch + stu[i].ma + stu[i].en;
    }
    sort(stu, stu + n, cmp);
    for (int i = 0; i < 5; i++) {
        cout << stu[i].id << " " << stu[i].sum << endl;
    }
    return 0;
}

总分相同，则比较语文，语文相同，则比较学号，由此编写比较函数，很基础很简单~~

2.谁拿了最多奖学金

样例输入

4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1

样例输出

ChenRuiyi
9000
28700

提交网址2

//有时间再写

3.大统领投票

样例输入

3
123456799
123456789132456789123456789
11111111111111

样例输出

2
123456789132456789123456789

提交网址3

//有时间再写