机试考点整理（2）——排序问题

女爷i 2021-12-04 01:53 265阅读 0赞

之前写的其他两篇排序博客：  
[经典排序总结][Link 1]  
[数据结构 | 第九章 内部排序][_ _]

**排序问题**  
C++中sort工具，头文件`<algorithm>`,sort可以排任何类型包括结构体。  
sort（arr+i,arr+j），即arr\[i\]到arr\[j-1\]被排序，其他保持不变。  
`sort（arr+i,arr+j，greater<int>（））`从大到小排序

> 求前k高分数的学生的平均分数

#include <cstdio>
    #include <algorithm>
    #include<functional>
    using namespace std;
    int score[35];
    int main()
    { 
    	int N,k ,sum;
    	scanf("%d",&N);
    	for(int i=0;i<N;i++)
    	{ 
    		scanf("%d",&score[i]);
    }
    	scanf("%d",&k);
    	sort(score,score+N,greater<int>());
    	sum=0;
    	for(int i=0;i<k;i++)
    	{ 
    		sum+=score[i];
    	}
    	printf("%.2f\n",1.0*sum/k);
    	return 0;
    
    }

自定义排序

bool cmp(int x,int y)
    {
    	return x>y;//注意不能x>=y,会有错误
    }

> 按照除3的余数大小排

#include <cstdio>
    #include <algorithm>
    #include<functional>
    using namespace std;
    int num[105];
    bool cmp(int x, int y)
    { 
    	if(x%3 !=y%3)
    	{ 
    		return x%3 <y%3;
    	}else
    	{ return x<y;}
    }
    int main()
    { 
    	int N;
    	scanf("%d",&N);
    	for(int i=0;i<N;i++)
    	{ 
    		scanf("%d",&num[i]);
    	}
    	sort(num,num+N,cmp);
    	for(int i=0;i<N;i++)
    	{ 
    		if(i !=N-1)
    		{ 
    		printf("%d ",num[i]);
    		}else { 
    			printf("%d\n",num[i]);
    		}
    	}
    	while(1)
    	getchar();
    }

结构体排序

#include <iostream>
    #include <algorithm>
    #include <string>
    #include<functional>
    using namespace std;
    
    struct Student{ 
    	string name;
    	int score[4];
    };
    bool cmp_name(Student x,Student y)
    { 
     return x.name< y.name;
    }
    bool cmp_score(Student x, Student y)
    { 
    	if(x.score[0]!=y.score[0])
    	{ 
    		return x.score[0]>y.score[0];
    	}
    	if(x.score[1]!=y.score[1])
    	{ 
    		return x.score[1]>y.score[1];
    	}
    	if(x.score[2]!=y.score[2])
    	{ 
    		return x.score[2]>y.score[2];
    	}
    	return x.score[3]>y.score[3];
    }
    int main()
    { 
    	Student stu[3];
    	for(int i=0;i<3;i++)
    	{ 
    		cin>>stu[i].name;
    		for(int j=0;j<4;j++)
    		{ 
    		cin>>stu[i].score[j];
    		}
    	}
    	sort(stu,stu+3,cmp_name);
    	sort(stu,stu+3,cmp_score);
    	for(int i=0;i<3;i++)
    	{ 
    		cout<<stu[i].name<<" ";
    		for(int j=0;j<4;j++)
    		{ 
    		cout<<stu[i].score[j]<<" ";
    		}
    		cout<<endl;
    	}
    	while(1)
    	getchar();
    }

#include <cstdio>
    #include <algorithm>
    using namespace std;
    struct Student{ 
    	char name[15];
    	int score[4];
    
    };
    
    bool cmp(Student x, Student y)
    { 
    	int sumx=x.score[0]+x.score[1]+x.score[2]+x.score[3];
    	int sumy=y.score[0]+y.score[1]+y.score[2]+y.score[3];
    	return sumx>sumy;
    }
    Student stu[50];
    int main()
    { 
    	int N;
    	scanf("%d",&N);
    	for(int i=0;i<N;i++)
    	{ 
    		scanf("%s",stu[i].name);
    		for(int j=0;j<4;j++)
    		{ 
    			scanf("%d",&stu[i].score[j]);
    		}
    	}
    	sort(stu,stu+4,cmp);
    	for(int i=0;i<3;i++)
    	{ 
    		printf("%s\n",stu[i].name);
    	}
    	while(1)
    	getchar();
    }

[Link 1]: https://blog.csdn.net/qq_43145926/article/details/89964296
[_ _]: https://blog.csdn.net/qq_43145926/article/details/96995918