题目的主要信息：

• 输入任意的名字-成绩序列，获得成绩从高到低或从低到高的排列
• 相同成绩都按先录入排列在前的规则处理
• 进阶要求：时间复杂度$O(nlo{g}_{2}n)O(nlog\_2n)$，空间复杂度$O(n)O(n)$

方法一：库函数

具体做法：

在vector数组中使用pair来记录名字和成绩，然后重载比较，有降序和升序两种函数，根据输入的flag决定调用降序还是升序，然后使用stable_sort函数对vector数组按照成绩进行稳定排序。

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

bool cmp0(const pair<string, int>& a, const pair<string, int>& b) { //重载降序比较
    return a.second > b.second;
}
 
bool cmp1(const pair<string, int>& a, const pair<string, int>& b) { //重载升序比较
    return a.second < b.second;
}
int main()
{
    int n, flag;
    while (cin >> n >> flag) { 
        vector<pair<string, int>> record(n); //记录名字和成绩
        for (int i = 0; i < n; i++) { //输入成绩
            string name;
            int grade;
            cin >> name;
            cin>> grade;
            record[i].first = name;
            record[i].second = grade;
        }
        if (flag == 0) { //根据flag决定升序还是降序
            stable_sort(record.begin(), record.end(), cmp0);
        }
        else {
            stable_sort(record.begin(), record.end(), cmp1);
        }      
        for (int i = 0; i < n; i++) { //输出
            cout << record[i].first << ' ' << record[i].second << endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，stable_sort使用的还是快排原理，复杂度还是$O(nlo{g}_{2}n)O(nlog\_2n)$
• 空间复杂度：$O(n)O(n)$，使用了长度为$nn$的数组

方法二：桶排序

具体做法：

因为每个人的分数只有0-100分，那么我们可以准备101个桶代表这些分数，将输入的人名分别加入对应的桶后面。

输出的时候，根据是升序还是降序，升序就从100分的桶开始往下，依次输出桶中的内容，降序则从0分开始，依次输出桶中的内容。

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

int main()
{
    int n, flag;
    while (cin >> n >> flag) { 
        vector<string> score[101]; // 准备0-100分的桶
        for(int i = 0; i < n; i++){ //输入n个数据
            string name;
            int grade;
            cin >> name >> grade;
            score[grade].push_back(name); //将相应分数后面加入名字
        }
        if(flag == 0){ //降序
            for(int i = 100; i >= 0; i--){ //从100开始依次输出每个名字和分数
                for(int j = 0; j < score[i].size(); j++)
                    cout << score[i][j] << " " << i << endl;
            }
        }else{ //升序
            for(int i = 0; i <= 100; i++){ //从0开始依次输出每个名字和分数
                for(int j = 0; j < score[i].size(); j++)
                    cout << score[i][j] << " " << i << endl;
            }
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历101个桶，外加每个桶中的人数，一共是$n+101n+101$次
• 空间复杂度：$O(n)O(n)$，桶空间为人数，总共$nn$个人