求助大佬们sort函数的详细用法

P1093 [NOIP2007 普及组] 奖学金

bluetored @ 2022-11-02 13:45:11

先抛出问题在阅读代码是我发现他的排序是从大到小的

sort函数里面在调用一个cmp函数,那么排序关系(从大到小,还是从小到大)与cmp是否有关系,又行该怎么区控制

代码是题解,我开始不会这个sort的用法,所以用了个快排(虽然没通过)

#include<bits/stdc++.h>
using namespace std;
struct stu{//学生信息
    int Id;
    int Chinese;
    int Math;
    int English;
    int Sum;
};stu a[301];
bool cmp(stu a,stu b)//上面已经解释过了
{
    if(a.Sum>b.Sum)
        return true;
    else if(a.Sum==b.Sum && a.Chinese>b.Chinese)
        return true;
    else if(a.Sum==b.Sum && a.Chinese==b.Chinese && a.Id<b.Id) 
        return true;
    else
        return false;
}
int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)//数据处理
    {
        scanf("%d%d%d",&a[i].Chinese,&a[i].Math,&a[i].English);
        a[i].Sum=a[i].Chinese+a[i].Math+a[i].English;
        a[i].Id=i;
    }
    sort(a+1,a+n+1,cmp);//STL最棒的快排
    for(i=1;i<=5;i++)
        printf("%d %d\n",a[i].Id,a[i].Sum);
    return 0;
}

我不懂原理,所以原谅我猜测只要把cmp函数定义的参数a , b互换位置就可以做到从小到大排序了。


by uid_310801 @ 2022-11-02 14:00:00

你只需要记住cmp(a,b){return a<b}是从小到大排序就行了


by Zvelig1205 @ 2022-11-02 14:09:20

@bluetored 我的建议是,先判断第一关键字是否相等,在判断第二关键字是否相等。

然后就可以写成这样:


bool cmp(data a,data b)
{
    if(a.x==b.x)
    {
        if(a.y==b.y)return a.z<b.z;
        else return a.y<b.y;
    }
    else return a.x<b.y;
}

by Yahbim @ 2022-11-02 14:20:47

cmp 定义了个全序关系,然后 sort 负责按所定义的全序关系排序,不保证此含义下相等元素的顺序


by Yahbim @ 2022-11-02 14:30:42

@bluetored 比如说,对于序列 A,你希望把序列排成 f(a_1)\le f(a_2)\le f(a_3)\le \dots\le f(a_n),那你就定义“x 小于 y”为“f(x)<f(y)”,然后 sort 就可以做到按你定义的大小关系排序了


by doubleki @ 2022-11-02 16:47:18

cmp要在你认为两个对象顺序正确时返回true,其余返回false,个人认为这样比较好记


|