题解 | #成绩排序#

利用归并排序，分别保证了时间复杂度和稳定性

#include<stdio.h>
typedef struct namegrade_ {
    char name[10];
    int grade;
}namegrade;
void msort(namegrade* arr, namegrade* buf, int L, int M, int R,int type) {
    if (L < M - 1)msort(arr, buf, L, L + (M - L >> 1), M,type);
    if (M < R - 1)msort(arr, buf, M, M + (R - M >> 1), R,type);
    if (L < R - 1) {
        int p1 = L, p2 = M, pbuf = L;
        while (p1 < M && p2 < R) {
            if(type==1)buf[pbuf++] = arr[p1].grade > arr[p2].grade ? arr[p2++] : arr[p1++];
            else buf[pbuf++] = arr[p1].grade < arr[p2].grade ? arr[p2++] : arr[p1++];
        }
        while (p1 < M)buf[pbuf++] = arr[p1++];
        while (p2 < R)buf[pbuf++] = arr[p2++];
        while (--pbuf >= L)arr[pbuf] = buf[pbuf];
    }
}
int main() {
    int sum, type;
    namegrade arr[200];
    while (scanf("%d %d", &sum, &type) != EOF) {
        for (int i = 0; i < sum; i++) {
            char str[10];

            scanf("%s %d", str, &arr[i].grade);
            int j = 0;
            while (str[j]) {
                arr[i].name[j] = str[j];
                j++;
            }
            arr[i].name[j] = 0;
        }
        namegrade buf[200];
        msort(arr, buf, 0, sum >> 1, sum,type);

        int i = 0;
        while (i<sum) {
            printf("%s %d\n", arr[i].name, arr[i].grade);
            i++;
        }
    }
}