题解 | 成绩排序

#include <stdio.h>
#include<stdlib.h>
#include <string.h>
typedef struct {
    char name[20];
    int score;
}P;
P p[200];


void printP(P p){
    printf("%s %d\n",p.name,p.score);
}

void StringSwap(char*s1,char*s2){
    char name_temp[20];
    strcpy(name_temp,s1);
    strcpy(s1,s2);
    strcpy(s2,name_temp);
}

void swap(P*p1,P*p2){
    // int temp=p1->score;
    // p1->score=p2->score;
    // p2->score=temp;
    // StringSwap(p1->name, p2->name);
    P temp=*p1;
    *p1=*p2;
    *p2=temp;
}

void asc(P*p,int l,int r){
    // if(l>=r) return;

    // int x=p[l].score,i=l-1,j=r+1;

    // while(i<j){
    //     do i++;while(p[i].score<x);
    //     do j--;while(p[j].score>x);
    //     if(i<j) swap(&p[i],&p[j]);
    // }

    // asc(p,l,j);
    // asc(p,j+1,r);
    if(l>=r) return;
    int mid=l+r>>1;
    asc(p, l, mid);
    asc(p,mid+1,r);
    int k=0,i=l,j=mid+1;
    P temp[200];
    while(i<=mid&&j<=r){
        if(p[i].score<=p[j].score) {temp[k].score=p[i].score;strcpy(temp[k++].name,p[i++].name);}
        else {temp[k].score=p[j].score;strcpy(temp[k++].name,p[j++].name);}
    }
    while (i<=mid) {temp[k].score=p[i].score;strcpy(temp[k++].name,p[i++].name);}
    while(j<=r){temp[k].score=p[j].score;strcpy(temp[k++].name,p[j++].name);}
    for(i=l,j=0;i<=r;i++,j++){swap(&p[i], &temp[j]);}

}

void desc(P*p,int l,int r){
    // if(l>=r) return;

    // int x=p[l].score,i=l-1,j=r+1;

    // while(i<j){
    //     do i++;while(p[i].score>x);
    //     do j--;while(p[j].score<x);
    //     if(i<j) swap(&p[i],&p[j]);
    // }

    // desc(p,l,j);
    // desc(p,j+1,r);
    if(l>=r) return;
    int mid=l+r>>1;
    desc(p, l, mid);
    desc(p,mid+1,r);
    int k=0,i=l,j=mid+1;
    P temp[200];
    while(i<=mid&&j<=r){
        if(p[i].score>=p[j].score) {temp[k].score=p[i].score;strcpy(temp[k++].name,p[i++].name);}
        else {temp[k].score=p[j].score;strcpy(temp[k++].name,p[j++].name);}
    }
    while (i<=mid) {temp[k].score=p[i].score;strcpy(temp[k++].name,p[i++].name);}
    while(j<=r){temp[k].score=p[j].score;strcpy(temp[k++].name,p[j++].name);}
    for(i=l,j=0;i<=r;i++,j++){swap(&p[i], &temp[j]);}
}

int main() {
    int num, flag;
    while (scanf("%d %d", &num, &flag) != EOF) { // 注意 while 处理多个 case
        for(int i=0;i<num;i++){
            scanf("%s %d",p[i].name,&p[i].score);
        }
        if(flag==1)asc(p,0,num-1);
        else desc(p,0,num-1);
        for(int i=0;i<num;i++){
            printP(p[i]);
        }
    }
    return 0;
}