题解 | #成绩排序#

成绩排序

http://www.nowcoder.com/practice/8e400fd9905747e4acc2aeed7240978b

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

#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++;
        }
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 14:00
不想多说了,什么逆天HR,还要教我礼貌😂
机械打工仔:这不纯傻卵吗,他还操心上别人老板了
投递BOSS直聘等公司7个岗位
点赞 评论 收藏
分享
06-25 16:25
梧州学院 Java
愿汐_:项目介绍那么长,然而你做了啥就一句话?
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务