《算法笔记》4.1小节——算法初步->排序
2020-04-08 本文已影响0人
木子李_0961
@[TOC]
Contest100000581 - 《算法笔记》4.1小节——算法初步->排序
1、讲解
4.1 .1 选择排序
选择排序
4.1.2 插入排序
插入排序
4.1.3 排序题与sort()函数的应用
1.相关结构体的定义
相关结构体的应用
2.cmp函数的编写
cmp函数
3.排名的实现
排名实现
2、例题
PATA 1025:
https://pintia.cn/problem-sets/994805342720868352/problems/994805474338127872
题析：很经典的题目，值得反复咀嚼
//1025PAT Ranking
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct student//学生结构体
{
char id[15];//准考证号
int score;
int loc_number;//考场号
int loc_rank;
}stu[30005];
/*
//The output must be sorted in nondecreasing order of the final ranks.
The testees with the same score must have the same rank, and the output
must be sorted in nondecreasing order of their registration numbers.
*/
bool cmp(student x,student y)//排序规则
{
if(x.score != y.score)
return x.score>y.score;
else
return strcmp(x.id,y.id)<0;
}
int main()
{
int n;
scanf("%d",&n);
int loc_sum=n;
int count=0;
while(n--)
{
int k;//各个考场人数
scanf("%d",&k);
// int count=0;//总数
for(int i=0;i<k;i++)//输入学生信息
{
scanf("%s %d",stu[count].id, &stu[count].score);
stu[count].loc_number = (loc_sum-n);//赋值考场号
count++;
}
sort(stu+count-k,stu+count,cmp);
stu[count-k].loc_rank = 1;//初始化各个考场排名
for(int j=count-k+1;j<count;j++)//赋予排名
{
if(stu[j].score == stu[j-1].score)//如果与前一位考生同分
stu[j].loc_rank = stu[j-1].loc_rank;//排名也相同
else//不同分，排名为该考生前的人数
stu[j].loc_rank = j+1-(count-k);
}
}
//输出要求
/*
For each test case, first print in one line the total number of testees.
Then print the final ranklist in the following format:
registration_number final_rank location_number local_rank
*/
printf("%d\n",count);//输出所有考生人数total number
sort(stu,stu+count,cmp);//所有考生排序
int r = 1;//当前考生排名
for(int i=0;i<count;i++)
{
if(i>0 && stu[i].score != stu[i-1].score)
r = i+1;
printf("%s ",stu[i].id);//registration_number
//location_number local_rank
printf("%d %d %d\n",r, stu[i].loc_number,stu[i].loc_rank);
}
return 0;
}
3、练习题
1923 Problem A 排序
来自 http://codeup.cn/contest.php?cid=100000581
题析：可以方便使用sort()函数
//1923ProblemA排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int arr[105];
int n;
while(scanf("%d",&n) != EOF)
{
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
sort(arr,arr+n);//sort()函数的使用
for(int i=0;i<n-1;i++)
printf("%d ",arr[i]);
printf("%d\n",arr[n-1]);
}
return 0;
}
1925 Problem B 特殊排序
来自 http://codeup.cn/contest.php?cid=100000581
//1925ProblemB特殊排序
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int arr[1005];
int n;
while(scanf("%d",&n)!=EOF)//多点测试
{
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
sort(arr,arr+n);//排序函数
printf("%d ",arr[n-1]);
if(n==1)//特殊情况的处理
printf("%d\n",-1);
else
{
for(int i=0;i<n-1;i++)
{
printf("%d",arr[i]);
if(i<n-2)
printf(" ");
else
printf("\n");
}
}
}
return 0;
}
1926 Problem C EXCEL排序
来自 http://codeup.cn/contest.php?cid=100000581
题析：模拟+sort+学生结构体 应用，很经典，字典序\同成绩之类的处理,strcmp(x,y)当x,y不相等时不为0，判断视为true
//1926ProblemCEXCEL排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct student
{
char id[10];//学号
char name[10];//姓名
int grade;//成绩
}stu[100005];
int c;
int cmp(student x,student y)
{
switch(c)
{//当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。
case 1://按学号递增排序
return strcmp(x.id,y.id)<0;break;//若str1=str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数
case 2://按姓名的非递减字典序排序
if(!strcmp(x.name,y.name))
return strcmp(x.id,y.id)<0;
else
return strcmp(x.name,y.name)<0;
break;
case 3://按成绩的非递减排序
if(x.grade!=y.grade)
return x.grade<y.grade;
else
return strcmp(x.id,y.id)<0;
break;
default:
break;
}
/*
//当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。
if(c==1)//按学号递增排序
return strcmp(x.id,y.id)<0;//若str1=str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数
else if(c==2)//按姓名的非递减字典序排序
{
if(!strcmp(x.name,y.name))
return strcmp(x.id,y.id)<0;
else
return strcmp(x.name,y.name)<0;
}
else if(c==3)//按成绩的非递减排序
{
if(x.grade!=y.grade)
return x.grade<y.grade;
else
return strcmp(x.id,y.id)<0;
}
*/
}
int main()
{
int n;
int count=1;
while(scanf("%d%d",&n,&c) != EOF && n!=0)
{
for(int i=0;i<n;i++)
{
scanf("%s %s %d",stu[i].id,stu[i].name,&stu[i].grade);
}
sort(stu,stu+n,cmp);
printf("Case %d:\n",count++);
for(int i=0;i<n;i++)
{
printf("%s %s %d\n",stu[i].id, stu[i].name, stu[i].grade);
}
}
return 0;
}
1927 Problem D 字符串内排序
来自 http://codeup.cn/contest.php?cid=100000581
题析：gets()/puts()应用，简单应用
//1927ProblemD字符串内排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
char str[205];
while(gets(str)!=NULL)
{
int len = strlen(str);
sort(str,str+len);
// printf("%s\n",str);
puts(str);
}
return 0;
}
1978 Problem E Problem B
来自 http://codeup.cn/contest.php?cid=100000581
题析：注意数组下标指针的意义，
隐含多点测试？？（单点测试错误50%）
Sort()函数的应用
//1978ProblemEProblem B
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int arr[15][15];
bool cmp(int x,int y)//从大到小的比较法则
{
return x>y;
}
int main()
{
int m;
while(scanf("%d",&m)!=EOF)//单点测试???
{
int sum_row[15]={0},sum_column[15]={0},sum_duijiao[2]={0};//行、列、对角和存储矩阵
int sum[25]={0};//最终和存储矩阵
int row_cnt=0,col_cnt=0,dj_cnt=0;//数组下标指针
int sum_ce=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&arr[i][j]);//输入方阵数据
sum_row[i]+=arr[i][j]; //求每行的和
// cout<<sum_row[i]<<" ";
// cout<<endl;
if(i==j)
sum_duijiao[0]+=arr[i][j];//主对角线的和
if(i+j==m-1)
sum_duijiao[1]+=arr[i][j];//次对角线的和
sum_column[j] += arr[i][j];//求每列的和，对于列下标j
// sum_column[int(j%(m-1))] += arr[i][j];//错误做法，没有搞清楚下标的机制
}
// cout<<sum_column[i]<<" ";
// cout<<endl;
// sum_ce+=sum_row[i];
}
// cout<<sum_ce<<endl;
int k=0;//最终数组的下标指针
//赋值转移给最终数组
for(int i=0;i<m;i++)
{
sum[k++]=sum_row[i];
}
for(int i=0;i<m;i++)
{
sum[k++]=sum_column[i];
}
for(int i=0;i<2;i++)
{
sum[k++]=sum_duijiao[i];
}
sort(sum,sum+k,cmp);//排序
for(int i=0;i<k;i++)//输出
{
printf("%d",sum[i]);
if(i<k-1)
printf(" ");
else
printf("\n");
}
}
return 0;
}
2043 Problem F 小白鼠排队
来自 http://codeup.cn/contest.php?cid=100000581
题析：
struct{}arr[];结构体、sort排序
注意结构体的排序规则
//2043ProblemF小白鼠排队
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct mouse//老鼠结构体
{
int weight;//体重
char color[15];//帽子颜色
}mou[105];
//bool cmp(int x,int y)//错误
bool cmp(mouse x,mouse y)//正确排序规则
{
return x.weight>y.weight;
}
int main()
{
char color[105];
int N;
while(scanf("%d",&N) != EOF)//多点输入
{
for(int i=0;i<N;i++)//输入信息
scanf("%d%s",&mou[i].weight,mou[i].color);
sort(mou,mou+N,cmp);//排序
for(int i=0;i<N;i++)//输出信息
printf("%s\n",mou[i].color);
// printf("\n");
}
return 0;
}
2069 Problem G 中位数
来自 http://codeup.cn/contest.php?cid=100000581
题析：
进行模拟，得注意数组下标的处理，从0开始与从1处理
从1开始的数组下标有利于奇偶处理。
//2069ProblemG中位数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int num[10005];
int N;
while(scanf("%d",&N) != EOF && N!=0)//多点测试
{
// getchar();//消除换行符的影响
// memset(num,0,sizeof(num));//初始化数组，可有可无
int result;
for(int i=1;i<=N;i++)//注意下标从1开始有助于下面处理
scanf("%d",&num[i]);
sort(num+1,num+N+1);//排序 ，上限为num+N+1,若为num+N，错误50%
if(N%2==0)//偶数，中间两个数
{
result = (num[N/2]+num[N/2+1])/2;
}
else//奇数，中间一个数
{
result = num[(N+1)/2];
}
printf("%d\n",result);
}
return 0;
}
2080 Problem H 整数奇偶排序
来自 http://codeup.cn/contest.php?cid=100000581
题析：
奇偶处理，sort()应用，注意下标初始化
多点测试的输入形式
//2080ProblemH整数奇偶排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
bool cmp_even(int x,int y)
{
return x>y;
}
bool cmp_odd(int x,int y)
{
return x<y;
}
int main()
{
int num[15];
while(scanf("%d%d%d%d%d%d%d%d%d%d",&num[0],&num[1],&num[2],&num[3],&num[4],&num[5],&num[6],&num[7],&num[8],&num[9]) != EOF)
{
int even_cnt=0,odd_cnt=0,cnt=0;
int even[10]={0},odd[10]={0};
for(int i=0;i<10;i++)
{
if(num[i]%2==0)//偶数
odd[odd_cnt++]=num[i];
else//奇数
even[even_cnt++]=num[i];
}
sort(even,even+even_cnt,cmp_even);//奇数从大到小排序
for(int i=0;i<even_cnt;i++)//从大到小输出奇数
printf("%d ",even[i]);
sort(odd,odd+odd_cnt,cmp_odd);//偶数排序
for(int i=0;i<odd_cnt-1;i++)//从小到大输出偶数
printf("%d ",odd[i]);
printf("%d\n",odd[odd_cnt-1]);
}
return 0;
}
2088 Problem I 排名
来自 http://codeup.cn/contest.php?cid=100000581
题析：
M、N不分，题中许多注释都是测试用的，因为M、N搞混了，注意细节的处理
//2088ProblemI排名
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct student
{
char id[25];//准考证号
int sol_p_n;//解决题目数
int p_id[15];//解决题目题号
int grade;//成绩
}stu[1005];
bool cmp(student x,student y)
{
if(x.grade!=y.grade)
return x.grade>y.grade;
else
return strcmp(x.id,y.id)<0;
}
int main()
{
int N,M,G;
int course_grad[15]={0};
while(scanf("%d%d%d",&N,&M,&G) != EOF && N!=0)
{
int pass_cnt=0;
for(int i=1;i<=M;i++)//各科分数
scanf("%d",&course_grad[i]);
// int count=0;
// cout<<M<<endl;
for(int i=0;i<N;i++)//输入处理
{
stu[i].grade=0;
scanf("%s%d",&stu[i].id,&stu[i].sol_p_n);
// cout<<stu[i].sol_p_n<<endl;
for(int j=0;j<stu[i].sol_p_n;j++)//输入解决的题
{
scanf("%d",&stu[i].p_id[j]);
stu[i].grade += course_grad[stu[i].p_id[j]];
// cout<<stu[i].grade<<endl;
}
if(stu[i].grade>=G)
pass_cnt++;
// cout<<pass_cnt<<endl;
// cout<<i<<endl;
// cout<<"46532"<<endl;
}
// cout<<"1312222"<<endl;
printf("%d\n",pass_cnt);
sort(stu,stu+N,cmp);
for(int i=0;i<N;i++)
{
if(stu[i].grade >= G)
printf("%s %d\n",stu[i].id,stu[i].grade);
}
}
return 0;
}
