蓝桥杯省赛备战笔记—— （三）使用sort排序

需要载入头文件

#include<algorithm>

一、使用

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int arr[] = {2,4,5,3,1};
    //sort(arr,arr+5);
    sort(arr + 1,arr + 4);
    for(int i = 0;i < 5;i++)
        cout <<arr[i]<<' ';
    return 0;
}

sort(arr,arr+5) ———— (数组名，数组名+长度) —— 将整个数组从小到大排序
sort(arr + i,arr + j) ———— 将arr[ i ] 到 arr[ j - 1 ] 排序，其余元素保持原位置不变

如果希望arr 中的元素 从大到小排序（或按照某一个规则排列），传入第3个参数 —— ”排序方法“

sort(arr,arr  + 5, greater<int>());

<int> 表示待排序的数组中的元素类型为 int

例题：前K名的平均成绩

#include<iostream> // 要载入这个头文件，否则dec_c++上会报错'greater'was not declared in this scope
#include<cstdio>
#include<algorithm>
using namespace std;
int s[35];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n;i++){
        scanf("%d",&s[i]);
    }
    sort(s,s+n,greater<int>());
    int k;
    scanf("%d",&k);
    int sum = 0;
    for(int i = 0; i < k;i++){
        sum += s[i];
    }
    printf("%.2f", 1.0 * sum / k);    
    return 0;
}

例题：分数段统计

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[35];
int b[7];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n,greater<int>());
    for(int i = 0; i < n;i++){
        printf("%d
",a[i]);
    }
    for(int i = 0; i < n;i++){
        if(a[i] == 100){
            b[1]++;
        }else if(a[i] >= 90 && a[i] <= 99 ){
            b[2]++;
        }else if(a[i] >= 80 && a[i] <= 89){
            b[3]++;
        }else if(a[i] >= 70 && a[i] <= 79){
            b[4]++;
        }else if(a[i] >= 60 && a[i] <= 69){
            b[5]++;
        }else{
            b[6]++;
        }
    }    
    for(int i = 1;i < 7;i++){
        if(i != 6)
            printf("%d ",b[i]);
        else
            printf("%d",b[i]);
    }    
    return  0;
}

二、第三个参数—— 自定义排序方法

在sort 第三个参数中传入 cmp ,sort 函数是系统定义好的，可以直接支持函数地址作为参数

bool cmp(int x,int y){
    return x > y;
    //注意： 此处不可出现等号'='
    //意思是：如果条件 x > y 成立，则 x 排在 y 前面 
}
int main(){
    ...
    sort (arr , arr + n, cmp);
    ... 
}

例题：整数排序

#include<stdio.h>
#include<algorithm>
using namespace std;
int s[105];
bool cmp(int x,int y){
    if(x % 3 != y  % 3){
        return x % 3 < y % 3;
    }else{
        return x < y;
    }
}
int main(){
    freopen("lab.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n;i++){
        scanf("%d",&s[i]);
    }
    sort(s,s + n,cmp);
    printf("%d",s[0]);
    for(int i = 1;i < n;i++){
        printf(" %d",s[i]);
    }
    return 0;
}

三、结构体的构造函数

构造函数是一种定义在结构体中的特殊函数，它可以被用于描述对结构体进行初始化的算法。

struct Student{
    int score;
    string name;
    Student(string n,int s){
        name = n;
        score = s;
    }
};

●函数名与结构体名完全相同
●不能定义返回值类型，也不能有return语句
●可以有形参，也可以没有形参，可以带有默认参数
●可以重载
在使用的时候，我们不需要手动调用构造函数。当我们创建结构体的时候，构造函数会自动被调用。

练习：读入多个学生姓名和成绩，反转输出成绩和姓名

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

struct Student{
    string name;
    int score;
    Student(){}
    Student(string n,int s):name(n),score(s){}
};
int main(){
    Student stu[3];
    for(int i = 0;i < 3;i++){
        int s;
        string n;
        cin>>n>>s;
        stu[i] = Student(n,s);
    }
    for(int i = 0;i < 3;i++){
        cout<< stu[i].score<<" "<<stu[i].name<<endl;
    }
    return 0;
}

练习：输出成绩单，按照姓名的字典序排序 ———— 结构体排序

#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
struct Student{
    string name;
    int score[2];
};
bool cmp(Student x,Student y){
    return x.name < y.name;
}
int main(){
    Student stu[4];
    for(int i =0; i < 4;i++){
        cin >> stu[i].name;
        for(int j = 0;j < 2;j++){
            cin >> stu[i].score[j];
        }
    }
    sort(stu,stu+4,cmp);
    for(int i = 0;i < 4;i++){
        cout<<stu[i].name<<" ";
        for(int j = 0; j < 2;j++){
            cout<<stu[i].score[j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

练习：复杂排序

其实就是改一下cmp 函数

bool cmp(Student x,Student y){
    if(x.score[0] != y.score[0])
        return x.score[0] > y.score[0];
    if(x.score[1] != y.score[1])
        return x.score[1] > y.score[0];
    if(x.score[2] != y.score[2])
        return x.score[2] > y.score[2];
    return x.score[3] > y.score[3];
}

例题：评奖

这道题，可以按照上方结构体排序做

但有个更方便的做法：

#include<stdio.h>
int sum[805] = {0};  
char name[45][15];

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n;i++){
        scanf("%s",name[i]);
        int all = 0;
        for(int j = 0; j < 4;j++){
            int k;
            scanf("%d",&k);
            all += k;
        }
        sum[all] = i;  
    }
    int f = 3;
    for(int i = 804; f > 0;i--){
        if(sum[i] != 0){
            f--;
            printf("%s
",name[sum[i]]);
        }
    }
    return 0;
}

就是利用标记数组，其中每科最大分数为200，所以总分最大为800 。标记数组中放置总分对应的名字在name数组中的下标，然后从后往前遍历得到3个下标，分别输出相应的名字即可