排序技巧——双关键字排序(快速排序,sort)

Background

• 在做题过程中，我们常会遇到对双关键字排序的情况，如：当分数相等时，序号小的在前.

• 这时我们可以通过定义cmp函数作为sort的参数进行排序.

  Solution

• 定义一个结构体，包含我们所需的关键字。例如，这是一个包含分数，序号和姓名的结构体.

struct node{
    int id,score;
    string name;
};

• 实现cmp函数，这里使用了两组不同的关键字.

bool cmp_score_id(node a,node b)
{
    if(a.score==b.score)return a.id<b.id;
    return a.score>b.score;
}
bool cmp_score_name(node a,node b)
{
    if(a.score==b.score)return a.name<b.name;
    return a.score>b.score;
}

• 代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int id,score;
    string name;
}stu[1000];
bool cmp_score_id(node a,node b)
{
    if(a.score==b.score)return a.id<b.id;
    return a.score>b.score;
}
bool cmp_score_name(node a,node b)
{
    if(a.score==b.score)return a.name<b.name;
    return a.score>b.score;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)//卡常小技巧，++i较i++更快.
        scanf("%d%d%s",&stu[i].id,&stu[i].score,&stu[i].name);
    sort(stu+1,stu+1+n,cmp_score_id);
    for(int i=1;i<=n;++i)printf("%d %d",stu[i].id,stu[i].score);
    sort(stu+1,stu+1+n,cmp_score_name);
    for(int i=1;i<=n;++i)printf("%d %s",stu[i].score,stu[i].name);
    return 0;      
}

• Jan,21,2017 Sun