1 按照 城市,学校,成绩作为关键字来排名
相当于:
struct Student{
int cityId;
int schoolId;
char grade;
int stuId;
bool operator<(const Student& s)const{
if(cityId==s.cityId){
if(schoolId==s.schoolId){
return grade<s.grade;
}
return schoolId<s.schoolId;
}
return cityId<s.cityId;
}
};
sort(students.begin(),students.end());
代码如下:
#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
struct Student{
int cityId;
int schoolId;
char grade;
int stuId;
};
ostream& operator << (ostream& os, const Student& obj)
{
os << "城市: "<<obj.cityId<<" 学校:"
<<obj.schoolId<<" 学生id:"<<obj.stuId<<
" 分数:"<<obj.grade;
return os;
}
int main(){
srand(time(NULL));
vector<Student> students;
for(int i=0;i<12;i++){
auto cid = rand() % 3 + 1;
auto sid = rand() % 6 + 1;
char g = 'A'+(rand() % 4 );
auto stuId = 1001001+i;
students.push_back({cid,sid,g,stuId});
}
for(auto& s:students){
cout<<s<<endl;
}
vector<Student> gBulket[4];
for(auto& s:students){
int gmod = s.grade-'A';
gBulket[gmod].push_back(s);
}
vector<Student> sBulket[7];
for(int i=0;i<4;i++){
for(int j=0;j<gBulket[i].size();j++){
auto& stu = gBulket[i][j];
sBulket[stu.schoolId].push_back(stu);
}
}
vector<Student> cBulket[5];
for(int i=1;i<7;i++){
for(int j=0;j<sBulket[i].size();j++){
auto& stu = sBulket[i][j];
cBulket[stu.cityId].push_back(stu);
}
}
//收集
students.clear();
for(int i=1;i<5;i++){
for(int j=0;j<cBulket[i].size();j++){
students.push_back(cBulket[i][j]);
}
}
cout<<"按关键字排好后:"<<endl;
for(auto& s:students){
cout<<s<<endl;
}
return 0;
}
输出结果:
城市: 2 学校:1 学生id:1001001 分数:D
城市: 1 学校:6 学生id:1001002 分数:D
城市: 1 学校:5 学生id:1001003 分数:D
城市: 1 学校:6 学生id:1001004 分数:A
城市: 2 学校:4 学生id:1001005 分数:C
城市: 1 学校:5 学生id:1001006 分数:B
城市: 2 学校:6 学生id:1001007 分数:C
城市: 2 学校:2 学生id:1001008 分数:A
城市: 1 学校:5 学生id:1001009 分数:C
城市: 3 学校:1 学生id:1001010 分数:D
城市: 1 学校:4 学生id:1001011 分数:A
城市: 1 学校:2 学生id:1001012 分数:D
按关键字排好后:
城市: 1 学校:2 学生id:1001012 分数:D
城市: 1 学校:4 学生id:1001011 分数:A
城市: 1 学校:5 学生id:1001006 分数:B
城市: 1 学校:5 学生id:1001009 分数:C
城市: 1 学校:5 学生id:1001003 分数:D
城市: 1 学校:6 学生id:1001004 分数:A
城市: 1 学校:6 学生id:1001002 分数:D
城市: 2 学校:1 学生id:1001001 分数:D
城市: 2 学校:2 学生id:1001008 分数:A
城市: 2 学校:4 学生id:1001005 分数:C
城市: 2 学校:6 学生id:1001007 分数:C
城市: 3 学校:1 学生id:1001010 分数:D
复杂度分析:
设数组长度为 n
第一关键字种类为 m
第二关键字种类 为 r
第三关键字种类 为 q
则复杂度为 O(nmr*q)
比较适合 n 比较大,但是 关键字个数不多的情况