知识回顾

1.cmp函数的书写

cmp函数可对基本数据类型、结构体类型、STL容器进行自定义规则排序
默认按照从小到大排序

1.从int型大到小排序

bool cmp(int a,int b){
      return a>b;//当a大于b时，把a放在b前
}

2.对double型从大到小排序

bool cmp(double a, double b){
      return a>b;
}

3.对char数组从大到小排序

bool char(char a, char b){
      return a>b;
}

4.结构体数组的排序

//定义一个结构体数组
struct node{
      int x,int y;
}stu[10];
//一级排序
bool cmp(node a,node b){
        return a.x>b.x;//按照x值从大到小排序 (一级排序)
}
//二级排序
bool cmp(node a,node b){
        if(a.x!=b.x) 
             return a.x>b.x;//   x不等时按x从大到小排序
        else 
             return a.y<b.y;//    x相等时按从小到大排序
}

5.容器的排序
在STL容器标准容器中，只有vector、string、deque是可以使用sort的
set、map本身有序，不允许sort排序

bool cmp(int a,int b){
      return a>b;//当a大于b时，把a放在b前
}
int main(){
vector<int>vi;
vi.push_back(3);
vi.push_back(2);
vi.push_back(2);
sort(vi.begin(),vi.end(),cmp);
for (int i = 0; i < 3; ++i){
    printf("%d ",vi[i]);
  }
return 0;
}
//输出3 2 1

6.string的排序

//string型数组默认按照字典序从小到大输出
string str[3]={"bbbb","cc","aaa"};
sort(str,str+3);
for (int i = 0; i < 3; ++i)
{
    cout<<str[i]<<endl;
}
//输出
aaa
bbbb
cc

按照字符串从小到大排序

bool cmp(string str1,string str2)
{
    return str1.length()<str2.length();// 按string 的长度从小到大排序
}
string str[3]={"bbbb","cc","aaa"};
sort(str,str+3,cmp);
for (int i = 0; i < 3; ++i)
{
    cout<<str[i]<<endl;
}
//输出
cc
aaa
bbb

举例

我们定义一个结构体类型Student，列举常用的cmp方法

struct Student
{
    char name[10];
    char id[10];
    int score;
    int grade[4];//4个分数
    int r;
}stu[100010];
bool cmp(Student a,Student b){
    if(a.score!=b.score)
        return a.score>b.score;
    else
        return strcmp(a.name<b.name)<0;
}
    // a.name的字典序小于b.name
    // strcmp是string.h头文件下用来比较两个char型数组字典序大小的
    // 当str1字典序等于str2字典序返回0,小于时返回一个负数，大于时返回一个正数
int now;
//对多个分数的排序
bool cmp( Student a,Student b){
        return a.grade[now]>b.grade[now] // stu数组按now号分数递减排序
}

//如果先比较字符数组
bool cmp( Student a,Student b){
    int s=strcmp(a.id,b.id);
    if(s!=0)
        return s<0;
    else if ()
        return ...；
    else
        return ...；
}

排名的实现

1.记录排名然后输出

//当分数不同是排名不同，当分数相同时排名相同，会占用同一个排名
stu[0].r=1; //第一个排名设为1，数组下标从0开始
for (int i = 1; i < count; ++i)//   i从1开始
{
    if(stu[i].score==stu[i-1].score){  
//当前个体分数与上一个相同，则排名等于上一个个体排名，否则当前个体的排名等于数组下标加1
        stu[i].r=stu[i-1].r;
    }else{
        stu[i].r=i+1;
    }
}

2.直接输出排名

int r=1;
for (int i = 0; i < count; ++i)
{
    if(i>0&&stu[i].score!=stu[i-1].score){
//当前个体不是第一个个体且当前个体的分数等于上一个个体的分数，那么令r等于数组下标加1
        r=r+1;
    }
    //输出当前个体信息，或者令stu[i].r=r也行
}

以上来源于《算法笔记》，如有错误欢迎指正～