【杭电oj】1872 - 稳定排序（结构体排序）_wygoj-程序员宅基地

技术标签：排序

稳定排序

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4632 Accepted Submission(s): 1802

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浙大研究生复试热身赛（2）——全真模拟

对于不稳定的排序，只是名字变了，分数不会变，所以用两个bool型的变量分别判断是否正确排序和是否稳定排序。

如果名字不正确但分数相同则不稳定排序，如果分数不正确就说明排序错误。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
	char name[55];
	int grade;
	int num;
}a[311];
bool cmp(node a,node b)
{
	if (a.grade != b.grade)
		return a.grade > b.grade;
	else
		return a.num < b.num;
}
int main()
{
	int n;
	bool flag1;		//是否正确排序 
	bool flag2;		//是否稳定排序 
	while (~scanf ("%d",&n))
	{
		flag1 = flag2 = true;
		for (int i = 0 ; i < n ; i++)
		{
			scanf ("%s %d",a[i].name,&a[i].grade);
			a[i].num = i;
		}
		sort (a,a+n,cmp);
		for (int i = 0 ; i < n ; i++)
		{
			char t1[55];
			int t2;
			scanf ("%s %d",t1,&t2);
			if (t2 != a[i].grade)
				flag1 = false;
			else if (strcmp (t1,a[i].name) != 0)
				flag2 = false;
		}
		if (!flag1)		//错误排序
		{
			printf ("Error\n");
			for (int i = 0 ; i < n ; i++)
				printf ("%s %d\n",a[i].name,a[i].grade);
		}
		else
		{
			if (flag2)
				printf ("Right\n");
			else
			{
				printf ("Not Stable\n");
				for (int i = 0 ; i < n ; i++)
					printf ("%s %d\n",a[i].name,a[i].grade);
			}
		}
	}
	return 0;
}

本文链接：https://blog.csdn.net/wyg1997/article/details/51168846

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

程序员必学！Gradle源码全解析，看看这篇文章吧！_gradle 6.7.1源码分析-程序员宅基地

文章浏览阅读154次。背景惯例，先简单陈述一下自己的，91年生人，164年三本毕业后在深圳工作，末流小公司，工资13k，无房，无车，无户口。那时候感觉生活也还行，父母有退休金，我基本上不用太操心，女朋友在一起很久了，很体贴，没有怎么要求我。本来生活就这样一帆风顺下去我就满足了，但是去年初，女朋友家里出了一些事情，一点积蓄全给她了，后面疫情来了，家里开始催婚了，我感觉到了压力。目前的工资无法满足生活，虽然这些年来有一点点的提升，但是，房价物价涨的更快，于是我决定跳槽。从去年年底开始瞎投简历，回顾了一下，一共投了33份简历_gradle 6.7.1源码分析

关于Loadrunner并发组函数web_concurrent的注意事项_web_concurrent_start-程序员宅基地

文章浏览阅读5k次。web_concurrent_start函数是并发组开始的标记。组中所有的函数是并发执行的，并发组的结束符为web_concurrent_end 函数。在并发组中，可以包含的函数有：web_url、web_submit_data、web_custom_request、web_create_html_param、web_create_html_param_ex、web_reg_save_param、..._web_concurrent_start

Delphi dbgrideh序号_dbgrideh增加序号和箭头-程序员宅基地

文章浏览阅读267次。数据库里面的数据没有序号的数据，在dbgrideh上新增一列自定义其字段，例如：id。在dbgrideh控件上的‘OnDrawColumnCell’事件下写下代码。在unidatesource的‘OnDataChange’事件下写下。if DataCol = 0 then //设置在第一列。在编码的开头定义i，为integer。_dbgrideh增加序号和箭头

samber/lo 库的使用方法：处理切片-程序员宅基地

文章浏览阅读1.4k次，点赞27次，收藏26次。是一个 Go 语言库，提供了一些常用的集合操作函数，如 Filter、Map 和 FilterMap。这个库函数太多，因此我决定按照功能分别介绍，本文介绍的是 samber/lo 库中处理切片的函数。主要参考库的README。_samber/lo

verilog乘法器以及booth编码改进_改进booth编码-程序员宅基地

文章浏览阅读4.6k次，点赞7次，收藏28次。第一章整数乘法器1.1 整数的概念整数在IEEE 的规定上有，短整数short integer , 中整数integer 和长整数long integer ，它们之间的关系如下：整数字节空间取值范围短整数一个字节-127 ~ 127中整数两个字节-32767~32767长整数和四个字节-2147483647~2147483647 在这里笔者以短整数..._改进booth编码

C语言课程笔记知识总结与感想_c语言知识点感想-程序员宅基地

文章浏览阅读1.3k次。 C数据类型。{常量与变量}第2章常量:整型常量: 有符号整型常量:默认int定义为有符号整数，无需使用signed. 无符号整型常量:不能表示成小于零的数。长整型常量。无符号长整型常量。实型..._c语言知识点感想