算法竞赛--排序

发表于 更新于 分类于 阅读次数：
本文字数： 5.1k 阅读时长 ≈ 5 分钟

选择排序(降序排序)

有n个数，总共需要进行n-1趟操作，每趟选出待排序部分中最小的元素，令其与a[i]进行交换，时间复杂度为O(n*n)。

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0;i<len-1;i++)
	{
		int k=i;
		for(int j=i+1;j<len;j++)
		{
			if(a[j]>=a[k])
				k=j;
		}
		int temp=a[k];
		a[k]=a[i];
		a[i]=temp;
	}

快速排序(降序排序)

有n个数，总共需要进行n-1趟操作，j假设每趟操作前i个元素是有序的，将第i+1位置的元素插入到前i个元素的适当位置。

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<len;i++)
	{
	 	int temp=a[i],j=i;
		while(j>0&&temp>a[j-1])
		{
			a[j]=a[j-1];
			j--;
		}
		a[j]=temp;	
	}

1.EXCEL排序

Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。

输入信息:

测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (N<=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。以下有N行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，同组测试中没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（闭区间[0, 100]内的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。

输出信息:

对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。

样例输入:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4 1
000001 Zhao 75
000004 Qian 88
000003 Li 64
000002 Sun 90
4 2
000005 Zhao 95
000011 Zhao 75
000007 Qian 68
000006 Sun 85
4 3
000002 Qian 88
000015 Li 95
000012 Zhao 70
000009 Sun 95
0 3

样例输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Case 1:
000001 Zhao 75
000002 Sun 90
000003 Li 64
000004 Qian 88
Case 2:
000007 Qian 68
000006 Sun 85
000005 Zhao 95
000011 Zhao 75
Case 3:
000012 Zhao 70
000002 Qian 88
000009 Sun 95
000015 Li 95

思路:根据题意不同的排序规则，分别编写cmp1,cmp2,cmp3,分别读入n和c的值,根据c的值选择排序规则.

注意:

1.多组输入,并且当n=0时结束.

2.开始我将学号定义为字符数组，后来发现学号为六位数，可以用%06d输出，则将学号改为int型接收.

3.写cmp2函数，字符数组居然直接用==号判断，导致一直WA50%。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct student
{
	int num;
	char name[10];
	int score;
}stu[100100];
bool cmp1(student a,student b)	//当 C=1 时，按学号递增排序
{
	return a.num<b.num;
}
bool cmp2(student a,student b) //当 C=2时，按姓名的非递减字典序排序,姓名相同，按学号递增.
{
	if(strcmp(a.name,b.name)!=0)
		return (strcmp(a.name,b.name))<0;
	else
		return a.num<b.num;
}
bool cmp3(student a,student b)//当 C=2时，按成绩的非递减字典序排序,成绩相同，按学号递增.
{
	if(a.score!=b.score)
		return a.score<b.score;
	else
		return a.num<b.num;
}
int main()
{
	int count=1,n,c;
	while(scanf("%d %d",&n,&c)==2 && n)
	{
		for(int i=0;i<n;i++)
			scanf("%d %s %d",&stu[i].num,stu[i].name,&stu[i].score);
		if(c==1)
			sort(stu,stu+n,cmp1);
		else if(c==2)
			sort(stu,stu+n,cmp2);
		else if(c==3)
			sort(stu,stu+n,cmp3);
		printf("Case %d:\n",count);
		for(int i=0;i<n;i++)
			printf("%06d %s %d\n",stu[i].num,stu[i].name,stu[i].score);
		count++;
	}
	return 0;
}

2.排名

今天的上机考试虽然有实时的Ranklist，但上面的排名只是根据完成的题数排序，没有考虑每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分数线的考生，并将他们的成绩按降序打印。

输入信息:

测试输入包含若干场考试的信息。每场考试信息的第1行给出考生人数N ( 0 < N < 1000 )、考题数M ( 0 < M < = 10 )、分数线（正整数）G；第2行排序给出第1题至第M题的正整数分值；以下N行，每行给出一名考生的准考证号（长度不超过20的字符串）、该生解决的题目总数m、以及这m道题的题号（题目号由1到M）。 当读入的考生人数为0时，输入结束，该场考试不予处理。

输出信息:

对每场考试，首先在第1行输出不低于分数线的考生人数n，随后n行按分数从高到低输出上线考生的考号与分数，其间用1空格分隔。若有多名考生分数相同，则按他们考号的升序输出。

样例输入:

1
2
3
4
5
6
3 5 32
17 10 12 9 15
CS22003 5 1 2 3 4 5
CS22004 3 5 1 3
CS22002 2 1 5
0

样例输出:

1
2
3
4
3
CS22003 63
CS22004 44
CS22002 32

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct student
{
	char num[25];
	int sum;			//存储总分
}stu[1005];
bool cmp(student x,student y)
{
	if(x.sum==y.sum)
		return strcmp(x.num,y.num)<0;
	else
		return x.sum>y.sum;
}
int main()
{
	int n;
	while(scanf("%d",&n)==1 && n)	//读取考生人数，人数为0时结束
	{
		int score[15]={0};
		int m,g,c=0;
		scanf("%d %d",&m,&g);
		for(int i=0;i<m;i++)			//接收1-M题的分数值，并存储
			scanf("%d",&score[i+1]);
		for(int i=0;i<n;i++)
		{
			int q,total=0,count;
			scanf("%s %d",stu[i].num,&count);//接收学生的考号及解决的题数
			while(count--)
			{
				scanf("%d",&q);		//接收题号，根据题号判断分数，并累加
				total+=score[q];
			}
			stu[i].sum=total;
			if(stu[i].sum>=g)
				c++;				//记录过线总人数
		}
		sort(stu,stu+m,cmp);	//进行排名
		printf("%d\n",c);
		for(int i=0;i<c;i++)
			printf("%s %d\n",stu[i].num,stu[i].sum);
	}	
	return 0;
}

3.日期排序

有一些日期，日期格式为 “MM/DD/YYYY”。编程将其按日期大小排列。

输入信息:

输入第一行一个整 n(1 \le n \le 1000)n(1≤n≤1000)，表示日期的个数。接下来 nn 行按照题目描述的格式输入 nn 个日期。

输出信息:

输出从早到晚排序后的日期，一个日期占一行，日期输出的格式和输入一样。

样例输入:

1
2
3
4
5
6
7
8
9
8
01/26/1998
09/26/1927
01/05/1927
04/16/2024
08/08/1993
01/01/2019
06/22/1973
07/16/2030

样例输出:

1
2
3
4
5
6
7
8
01/05/1927
09/26/1927
06/22/1973
08/08/1993
01/26/1998
01/01/2019
04/16/2024
07/16/2030

注意:

该题的主要难度在与cmp函数的书写，分别对年月日进行处理，完成对日期排序。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <algorithm>
using namespace std;
struct date
{
	int year;
	int month;
	int day;
}d[1010];
bool cmp(date a,date b)
{
	if(a.year==b.year)
	{
		if(a.month==b.month)
			return a.day<b.day;
		else
			return a.month<b.month;
	}
	else
		return a.year<b.year; 
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d/%d/%d",&d[i].month,&d[i].day,&d[i].year);
	sort(d,d+n,cmp);
	for(int i=0;i<n;i++)
		printf("%02d/%02d/%d\n",d[i].month,d[i].day,d[i].year);
}
小礼物走一个哟
0%