题解 | 成绩排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char name[100];
    int score;
    int index;
} Student;

// 降序比较函数
int compare_desc(const void *a, const void *b) {
    Student *s1 = (Student *)a, *s2 = (Student *)b;
    return s1->score != s2->score ? s2->score - s1->score : s1->index - s2->index;
}

// 升序比较函数  
int compare_asc(const void *a, const void *b) {
    Student *s1 = (Student *)a, *s2 = (Student *)b;
    return s1->score != s2->score ? s1->score - s2->score : s1->index - s2->index;
}

// 主处理函数
void fun(int n, int sort_type, Student students[]) {
    qsort(students, n, sizeof(Student), sort_type ? compare_asc : compare_desc);
    for (int i = 0; i < n; i++) {
        printf("%s %d\n", students[i].name, students[i].score);
    }
}

int main() {
    int n, sort_type;
    while (scanf("%d%d", &n, &sort_type) != EOF) {
        Student *students = malloc(n * sizeof(Student));
        for (int i = 0; i < n; i++) {
            scanf("%s%d", students[i].name, &students[i].score);
            students[i].index = i;
        }
        fun(n, sort_type, students);
        free(students);
    }
    return 0;
}

排序算法实现

使用C标准库的qsort函数，基于快速排序算法：

qsort(students, n, sizeof(Student), sort_type ? compare_asc : compare_desc);

排序算法要点：

1. 快速排序：平均时间复杂度：O(n log n)，空间复杂度：原地排序

2. 稳定性保证：在结构体中添加index字段记录输入顺序，比较时作为第二排序条件

// 主要排序条件：成绩

if (s1->score != s2->score)

return s2->score - s1->score; // 降序

// 次要排序条件：输入顺序（保证稳定性）

return s1->index - s2->index;

3. 动态排序：sort_type = 0 → 使用compare_desc降序；sort_type = 1 → 使用compare_asc升序

其余问题

问题1：需要循环处理未知数量的测试用例

解决：使用while(scanf(...) != EOF)持续读取直到文件结束

问题2：学生数量不固定，可能很大

解决方案：使用malloc动态分配，避免栈溢出