信息学奥赛⼀本通C++语⾔——1183：病⼈排队
【题⽬描述】
病⼈登记看病，编写⼀个程序，将登记的病⼈按照以下原则排出看病的先后顺序： 1.⽼年⼈（年龄 >= 60岁）⽐⾮⽼年⼈优先看病。
2.⽼年⼈按年龄从⼤到⼩的顺序看病，年龄相同的按登记的先后顺序排序。 3.⾮⽼年⼈按登记的先后顺序看病。
【输⼊】
第1⾏，输⼊⼀个⼩于100的正整数，表⽰病⼈的个数；
后⾯按照病⼈登记的先后顺序，每⾏输⼊⼀个病⼈的信息，包括：⼀个长度⼩于10的字符串表⽰病⼈的ID（每个病⼈的ID各不相同且只含数字和字母），⼀个整数表⽰病⼈的年龄，中间⽤单个空格隔开。
【输出】
按排好的看病顺序输出病⼈的ID，每⾏⼀个。
【输⼊样例】
5
021075 40
004003 15
010158 67
021033 75
102012 30
【输出样例】
021033
010158
021075
004003
102012
【源代码】
⽅法⼀：稳定排序(归并排序算法)
#define SIZEN 110
struct patient {
char id[12];
int age;
};
void merge_sort(patient *arr, patient *tmp,const int s,const int e);//定义归并排序函数int main(){ int n;
char pid[12];
int num,op=0,ns=0;
patient old_people[SIZEN],non_senile[SIZEN];
memset(non_senile,0,sizeof(non_senile));
memset(old_people,0,sizeof(old_people));
cin>>n;
for(int i=0; i<n; i++){
cin>>pid;
cin>>num;
if(num>=60){//⼤于60岁放⼊⽼年⼈
old_people[op].age=num;
strcpy(old_people[op].id,pid);
op++;
}else{//否则放⼊⾮⽼年⼈
non_senile[ns].age=num;
strcpy(non_senile[ns].id,pid);
ns++;
}
}
patient old_tmp[SIZEN];//临时数组
merge_sort(old_people,old_tmp,0,op-1);//调⽤归并排序函数
for(int i=op-1; i>=0; i--){
cout<<old_people[i].id<<endl;//⽼年⼈优先，按年龄从⼤到⼩
}
for(int i=0; i<ns; i++){
cout<<non_senile[i].id<<endl;//⾮⽼年⼈按录⼊顺序
}
return0;
}
void merge_sort(patient *arr, patient *tmp,const int s,const int e){
if(s >= e)return;//start必须⽐end⼩，只有⼀个元素，直接返回
int m =(s+e)/2;//计算middle，向下取整 /**分解 Divide**/
merge_sort(arr, tmp, s, m);//递归左序列
merge_sort(arr,tmp, m+1, e);//递归右序列
int i = s,j = m +1;//左边index i 左边index j /**合并 Merge**/
int t = s;//临时数组index k
while(i <= m && j <= e)//按照年龄排序，从⼤到⼩
tmp[t++]=(arr[i].age < arr[j].age)? arr[i++]: arr[j++];
while(i <= m) tmp[t++]= arr[i++];//复制左边剩余 while(j <= e) tmp[t++]= arr[j++];//复制右边剩余
for(t = s; t <= e; t++){/**复制回原数组**/
arr[t]= tmp[t];
}
}
⽅法⼆：稳定排序(冒泡排序算法)
#define SIZEN 110
struct patient {
char id[12];
int age;
};
void bubble_sort(patient *arr,const int len);//定义冒泡排序函数int main(){
int n;
char pid[12];
int num,op=0,ns=0;
patient old_people[SIZEN],non_senile[SIZEN];
memset(non_senile,0,sizeof(non_senile));
memset(old_people,0,sizeof(old_people));
cin>>n;
for(int i=0; i<n; i++){
cin>>pid;
cin>>num;
if(num>=60){//⼤于60岁放⼊⽼年⼈
old_people[op].age=num;
strcpy(old_people[op].id,pid);
op++;
}else{//否则放⼊⾮⽼年⼈
non_senile[ns].age=num;
strcpy(non_senile[ns].id,pid);
ns++;
}
}
bubble_sort(old_people,op);//调⽤冒泡排序函数
for(int i=0; i<op; i++){
cout<<old_people[i].id<<endl;//⽼年⼈优先，按年龄从⼤到⼩}
for(int i=0; i<ns; i++){
cout<<non_senile[i].id<<endl;//⾮⽼年⼈按录⼊顺序
}
return0;
}
void bubble_sort(patient *arr,const int len){//冒泡排序算法bool ok;//是否有序的标志
for(int i=len-1; i>=0; i--){//从右向左轮询
ok=true;
for(int j=0; j<i; j++){//从左向右冒泡
if(arr[j].age<arr[j+1].age){//从⼤到⼩排序
swap(arr[j],arr[j+1]);
ok=false;
}
}
if(ok)break;
}
return;
}
⽅法三：稳定排序(插⼊排序算法)
#define SIZEN 110
struct patient {
char id[12];
int age;
};
void insert_sort(patient *arr,const int len);//定义插⼊排序函数
int main(){
int n;
char pid[12];
int num,op=0,ns=0;
patient old_people[SIZEN],non_senile[SIZEN];
memset(non_senile,0,sizeof(non_senile));
memset(old_people,0,sizeof(old_people));
cin>>n;
for(int i=0; i<n; i++){
cin>>pid;
cin>>num;
if(num>=60){//⼤于60岁放⼊⽼年⼈
op++;
old_people[op].age=num;
strcpy(old_people[op].id,pid);
}else{//否则放⼊⾮⽼年⼈
ns++;
non_senile[ns].age=num;
strcpy(non_senile[ns].id,pid);
}
}
insert_sort(old_people,op);//调⽤插⼊排序函数
for(int i=1; i<=op; i++){
cout<<old_people[i].id<<endl;//⽼年⼈优先，按年龄从⼤到⼩
}
for(int i=1; i<=ns; i++){
cout<<non_senile[i].id<<endl;//⾮⽼年⼈按录⼊顺序
}
return0;
}
void insert_sort(patient *arr,const int len){//插⼊排序算法
int i,j;
for(i=2; i<=len; i++){//默认第1个元素有序
arr[0]=arr[i];//arr[0]作为哨兵sentinel
for(j=i-1; arr[j].age<arr[0].age; j--){//arr[0]作为哨兵，不需要判断j>=0
arr[j+1]=arr[j];//后移
}
if(j!=i-1)arr[j+1]=arr[0];//插⼊
}
return;
}
⽅法四：不稳定排序(测试时有可能通不过，这⾥仅展⽰不稳定排序)
struct patient {
char id[10];
int age;
};
void selectsort(patient *arr,int n);//定义选择排序函数
int main(){
int n;
char pid[12];
int num,op=0,ns=0;
patient old_people[110],non_senile[110];
// memset(non_senile,0,sizeof(non_senile));
// memset(old_people,0,sizeof(old_people));
cin>>n;
for(int i=0; i<n; i++){
cin>>pid;
cin>>num;
if(num>=60){//⼤于60岁放⼊⽼年⼈
old_people[op].age=num;
strcpy(old_people[op].id,pid);
op++;
}else{//否则放⼊⾮⽼年⼈
non_senile[ns].age=num;
strcpy(non_senile[ns].id,pid);
ns++;
}
}
selectsort(old_people,op);//调⽤选择排序函数
for(int i=0; i<op; i++){
cout<<old_people[i].id<<endl;//⽼年⼈优先，按年龄从⼤到⼩}
for(int i=0; i<ns; i++){
cout<<non_senile[i].id<<endl;//⾮⽼年⼈按录⼊顺序
}
return0;
}
void selectsort(patient *arr,int n){//选择排序函数
int x;
for(int i=0; i<n; i++){
x=i;
for(int j=i+1; j<n; j++){
if(arr[j].age>arr[x].age){//按年龄从⼤到⼩排序
x=j;
}
}
if(x!=i){
swap(arr[i],arr[x]);
}
}
return;
}
