题解 | 用归并排序解决#成绩排序#

这道题可以用c++的 sort函数+自定比较条件解决，这是目前为止我看到的最快、最简洁的答案。
不过本人较熟悉c，所以尝试用c的归并排序方法解决。

#include <stdio.h>
struct Student{ //将接收数据的结构体定义为全局变量，可在调用函数中直接使用，避免传参出错
    char name[20];
    int score;
}student[1000];

void combine(int a,int left,int right){
    int i =0;
    int k=left;
    int mid=(left+right)/2;
    int j=mid+1;
    struct Student temp[1000];
    while (k<mid+1&&j<=right){ //这里统一先按升序排序建立临时数组temp，如果这里就分降序升序两种情况，会使代码变得复杂
            if(student[k].score<student[j].score){
                temp[i++]=student[k++];
            }else if (student[k].score>student[j].score){
                temp[i++]=student[j++];
            }else{ //与通常的归并排序不同，为保证排序的稳定性，列出当数值相同的情况。升序排序：下标小的值先放入临时数组；降序排序：下标大的值先放入临时数组（因为降序后面还要再次反转）
                if (a==1){ 
                    temp[i++]=student[k++]; //升序
                }
                else{
                    temp[i++]=student[j++]; //降序
                }
            }
        }
    while (j<=right){
            temp[i++]=student[j++];
        }
    while (k<mid+1){
            temp[i++]=student[k++];
    }
     for (i=0;i<=right-left;i++){ //将临时数组的值返回，i最大值为left到right的元素个数-1
            student[left+i]=temp[i];
        }
}
   
void scoresort(int a,int left,int right){  //归并排序
    if (left>=right){
        return;
    }
    int mid=(left+right)/2;
        scoresort(a,left, mid);
        scoresort(a,mid+1, right);
        combine(a,left,right);
}

int main() {
    int number,order;
    while (scanf("%d", &number) != EOF) {//多组输入值
        scanf("%d", &order);
        int i=0;
        while (i<number){ 
            scanf("%s %d",&student[i].name,&student[i].score);
                i++;
            }      
        int k;
        scoresort(order,0,number-1);//调用归并排序函数
        if(order ==0){ //若为降序排序，此处需对排序后的升序序列进行反转
            for (k=0;k<number/2;k++){
                student[number]=student[k];
			    student[k]=student[number-1-k];
                student[number-1-k]=student[number];
            }
        }
        for(k=0;k<number;k++){  //输出
            printf("%s %d\n",student[k].name,student[k].score);
        }
    }
    return 0;
}