点击打开链接

                                            稳定排序                               

大家都知道，快速排序是不稳定的排序方法。  如果对于数组中出现的任意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

ps: sort 排序是不稳定  ， 用插入排序或者冒泡都可以， 不过前提是数据不会太大， 要不然会超限 。目前只想到之一种解题方法， 等有了更好的再更新。

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; struct Stu { char name[55]; int sore; }; Stu stu1[303],stu2[303]; int main() { int n,i,j; while(scanf("%d",&n)!=EOF) { for( i=0;i<n;i++) { scanf("%s %d",&stu1[i].name ,&stu1[i].sore ); } for( i=0;i<n;i++) { scanf("%s %d",&stu2[i].name ,&stu2[i].sore ); } //插入排序 for( i=1;i<n;i++) { Stu key=stu1[i]; int j=i-1; while(j>=0&&stu1[j].sore<key.sore) { stu1[j+1]=stu1[j]; j--; } stu1[j+1]=key; } int a=0; int b=0; for( i=0;i<n;i++) if(strcmp (stu1[i].name , stu2[i].name) !=0 ) { a++; break; } for( i=0;i<n;i++) if(stu1[i].sore != stu2[i].sore ) { b++; break; } // printf("%d %d\n",a,b); if(b==0) { if(a==0) printf("Right\n"); else if(a==1) { printf("Not Stable\n"); for( j=0;j<n;j++) printf("%s %d\n",stu1[j].name,stu1[j].sore ); } } else if(b==1) { printf("Error\n"); for( j=0;j<n;j++) printf("%s %d\n",stu1[j].name,stu1[j].sore ); } } return 0; }