稳定排序

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 51 Accepted Submission(s) : 19

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

大家都知道，快速排序是不稳定的排序方法。
如果对于数组中出现的任意a[i],a[j](i<j),其中a[i]==a[j]，在进行排序以后a[i]一定出现在a[j]之前，则认为该排序是稳定的。

某高校招生办得到一份成绩列表，上面记录了考生名字和考生成绩。并且对其使用了某排序算法按成绩进行递减排序。现在请你判断一下该排序算法是否正确，如果正确的话，则判断该排序算法是否为稳定的。

Input

本题目包含多组输入，请处理到文件结束。
对于每组数据，第一行有一个正整数N(0<N<300)，代表成绩列表中的考生数目。
接下来有N行，每一行有一个字符串代表考生名字(长度不超过50，仅包含'a'~'z'),和一个整数代表考生分数(小于500)。其中名字和成绩用一个空格隔开。
再接下来又有N行，是上述列表经过某排序算法以后生成的一个序列。格式同上。

Output

对于每组数据，如果算法是正确并且稳定的，就在一行里面输出"Right"。如果算法是正确的但不是稳定的，就在一行里面输出"Not Stable"，并且在下面输出正确稳定排序的列表，格式同输入。如果该算法是错误的，就在一行里面输出"Error",并且在下面输出正确稳定排序的列表，格式同输入。

注意，本题目不考虑该排序算法是错误的，但结果是正确的这样的意外情况。

Sample Input

3
aa 10
bb 10
cc 20
cc 20
bb 10
aa 10
3
aa 10
bb 10
cc 20
cc 20
aa 10
bb 10
3
aa 10
bb 10
cc 20
aa 10
bb 10
cc 20

Sample Output

Not Stable
cc 20
aa 10
bb 10
Right
Error
cc 20
aa 10
bb 10

Author

linle

Source

2008浙大研究生复试热身赛

解题思路：

现将输入的数据进行稳定排序；

然后与他提供的结果进行比较；

#include<iostream>
#include<string>
using namespace std;
struct student
{
    string name;
    int score;
};
int check(student const a[],student const b[],int const num)
{

    for(int o=0;o<num;o++)
    {
        if(a[o].score!=b[o].score&&a[o].name!=b[o].name)
        {
            return 0;//分数不同,名字不同，排序结果错误
        
        }
    
    
    }
    for(int p=0;p<num;p++)
    {
        if(a[p].score==b[p].score&&a[p].name!=b[p].name)
        {
            return 1;//分数相同但名字不同 不稳定

        
        }
    
    
    }
    return 2;
    


}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        student exam[305],text[305];
        for(int i=0;i<n;i++)
        {
            cin>>exam[i].name>>exam[i].score;

        }
        for(int j=0;j<n;j++)
        {
            cin>>text[j].name>>text[j].score;
        
        }
    
        int ii,jj;
           student c;
        for(ii=0;ii<n;ii++)
        {
    
        for(jj=0;jj<n-ii-1;jj++)
        {
            if(exam[jj].score<exam[jj+1].score)
            {
                c.name=exam[jj].name;
                c.score=exam[jj].score;
                exam[jj].name=exam[jj+1].name;
                exam[jj].score=exam[jj+1].score;
                exam[jj+1].name=c.name;
                exam[jj+1].score=c.score;

            
            }
        
        }
        
        }//稳定排序
            /*cout<<"排序"<<endl;
             for(int k=0;k<n;k++)
            {
            cout<<exam[k].name<<exam[k].score<<endl;
            }*/

        //检查；
        int base;
        base=check(exam,text,n);
        if(base==2) printf("Right
");
        if(base==1)
        {
            printf("Not Stable
");
            for(int ww=0;ww<n;ww++)
            {
            cout<<exam[ww].name<<" "<<exam[ww].score<<endl;
            }
        
        
        }
        if(base==0)
        {
            printf("Error
");
            for(int qw=0;qw<n;qw++)
            {
            cout<<exam[qw].name<<" "<<exam[qw].score<<endl;
            }
                
        
        }

        
    
    
    
    }

    



return 0;
}