题目描述

要求相同成绩排序后相对位置不变也就是稳定排序，分为从大到小排序和从小到大排序两种，取决于输入

输入样例1：

4
0
jack 70
peter 96
Tom 70
smith 67

输出样例1：

peter 96
jack 70
Tom 70
smith 67

知识点

结构体

定义了一个名为Person的结构体，包含两个成员变量：
name（字符串类型，存储姓名）和score（整型，存储分数）。
重载了小于(<)和大于(>)操作符，使得Person对象之间可以直接进行比较。

greater<Person>() 在 C++ 中是一个函数对象（也称为仿函数），它用于比较两个 Person 类型的对象。它是 std::greater 特化版本，用于自定义类型的比较。当使用 greater[HTML_REMOVED]() 时，它实际上会比较两个 Person 对象的 score 成员变量，因为 Person 结构体中重载了 > 操作符。

在这个例子中，由于 Person 结构体已经重载了 > 操作符，所以greater<Person>() 将会使用这个重载的操作符来比较两个 Person 对象。具体来说，greater<Person>()(a, b) 会返回 true 如果 a.score > b.score，否则返回 false。

定义了一个Person类型的数组q，长度为N。

库函数

stable_sort()稳定排序，
底层实现：检查元素数量，小于32则为插入排序
如果大于32则进行归并排序
使用stable_sort函数对q数组中的Person对象按分数降序排序，
并使用了greater<Person>()作为比较函数

算法1

(归并排序/插入排序) $O(nlogn/n^2)$

C++ 代码

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

const int N=1010;
int n,m;
struct Person
{
    string name;
    int score;
    bool operator<(const Person &t)const
    {
        return score<t.score;
    }
    bool operator>(const Person&t)const
    {
        return score>t.score;
    }
}q[N];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>q[i].name>>q[i].score;
    if(!m)stable_sort(q,q+n,greater<Person>());
    else stable_sort(q,q+n);
    for(int i=0;i<n;i++)
    {
        cout<<q[i].name<<" "<<q[i].score;

    }
    return 0;
}

算法2

(快速排序sort函数) $O(nlogn)$

关键点多增加了一个id用于特判分数相同情况

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
struct Stu
{
    string name;
    int score;
    int id;

    bool operator< (const Stu& t) const
    {
        if (score != t.score) return score < t.score;
        return id < t.id;
    }

    bool operator> (const Stu& t) const
    {
        if (score != t.score) return score > t.score;
        return id < t.id;
    }
}s[N];

int main()
{
    int n, op;
    cin >> n >> op;
    for (int i = 0; i < n; i ++ ) cin >> s[i].name >> s[i].score, s[i].id = i;

    if(!op) sort(s, s + n, greater<Stu>());
    else sort(s, s + n);

    for (int i = 0; i < n; i ++ ) cout << s[i].name << " " << s[i].score << endl;

    return 0;
}