保研机试备考一：排序

保研机试备考一：排序 排序：AcWing 3375. 成绩排序 题目

https://www.acwing.com/problem/content/3378/

---

思路

给定学生的成绩单，成绩单中包含每个学生的姓名和分数，请按照要求将成绩单按成绩从高到低或从低到高的顺序进行重新排列。

对于成绩相同的学生，无论以哪种顺序排列，都要按照原始成绩单中靠前的学生排列在前的规则处理。

这题考察了哪种排序能保证相同元素的相对顺序不发生变化
这题一定要使用稳定排序，稳定排序的定义就是对于相同元素，它们的相对顺序不能发生变化。

不稳定排序	稳定排序
快速排序	归并排序
堆排序	stable_sort(C++ 库)
sort	冒泡排序

---

代码

自己写的代码：结构体冒泡排序

#include
#include
#include
using namespace std;
const int N=1010;
struct Transcript
{
    string name;
    int score;
}Transcripts[N];
int n,mode;
void bsup()
{
    bool flag=false;
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<n-1-i;j++)
        {
            if(Transcripts[j].score>Transcripts[j+1].score)
            {
                flag=true;
                swap(Transcripts[j],Transcripts[j+1]);
            }
        }
        if(flag==false)
            return;
    }
}
void bsdown()
{
    bool flag=false;
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<n-1-i;j++)
        {
            if(Transcripts[j].score<Transcripts[j+1].score)
            {
                flag=true;
                swap(Transcripts[j],Transcripts[j+1]);
            }
        }
        if(flag==false)
            return;
    }
}
int main()
{
    scanf("%d%d",&n,&mode);
    for(int i=0;i<n;i++)
        cin>>Transcripts[i].name>>Transcripts[i].score;
    if(mode)
        bsup();
    else
        bsdown();
    for(int i=0;i<n;i++)
        cout<<Transcripts[i].name<<" "<<Transcripts[i].score<<endl;
    return 0;
}

y总代码：stable_sort(C++ 库，内部用归并排序实现)

#include
#include
#include
using namespace std;
const int N=1010;
struct Person
{
    string name;
    int score;
    bool operator<(const Person& w) const
    {
        return score<w.score;
    }
    bool operator>(const Person& w) const
    {
        return score>w.score;
    }
}p[N];
int n,mode;
int main()
{
    cin>>n>>mode;
    for(int i=0;i<n;i++)
        cin>>p[i].name>>p[i].score;
    if(mode)
        stable_sort(p,p+n);
    else
        stable_sort(p,p+n,greater<Person>());
    for(int i=0;i<n;i++)
        cout<<p[i].name<<" "<<p[i].score<<endl;
    return 0;
}

依然可以使用sort实现稳定排序，重载一下运算符，把下标考虑进来

#include
#include
#include
using namespace std;
const int N=1010;
struct Person
{
    int id;         //加一下下标id
    string name;
    int score;
    bool operator<(const Person& w) const
    {
        if(score!=w.score) return score<w.score;
        return id<w.id;   //如果相同，下标在前面的放前面
    }
    bool operator>(const Person& w) const
    {
        if(score!=w.score) return score>w.score;
        return id<w.id;  //如果相同，下标在前面的放前面
    }
}p[N];
int n,mode;
int main()
{
    cin>>n>>mode;
    for(int i=0;i<n;i++)
    {
        cin>>p[i].name>>p[i].score;
        p[i].id=i;  //把下标也放进去
    }
    if(mode)
        sort(p,p+n);
    else
        sort(p,p+n,greater<Person>());
    for(int i=0;i<n;i++)
        cout<<p[i].name<<" "<<p[i].score<<endl;
    return 0;
}

---

排序：AcWing 3376. 成绩排序2 题目

https://www.acwing.com/problem/content/3379/

---

思路

使用sort，重载<运算符，这题比较直接，不多说啦。

---

代码

#include
#include
using namespace std;
const int N=110;
struct student
{
    int id;
    int score;
    bool operator <(const student& w)const
    {
        if(score!=w.score) return score<w.score;
        return id<w.id;
    }
}p[N];
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i].id>>p[i].score;
    sort(p,p+n);
    for(int i=0;i<n;i++)
        cout<<p[i].id<<" "<<p[i].score<<endl;
    return 0;
}

---