PAT 1028 List Sorting 題解：學生資料多鍵值排序

題目大意

模擬 Excel 欄位排序功能。給定 N 筆學生資料（六位數學號、姓名、分數），依指定欄位 C 排序：

• C=1：按學號遞增
• C=2：按姓名非遞減，同名按學號遞增
• C=3：按分數非遞減，同分按學號遞增

N ≤ 100,000，需高效排序。

解題思路

定義學生結構體，使用 qsort 搭配三種比較函數：

typedef struct {
    int id, score;
    char name[10];
} Student;

int cmp1(const void* a, const void* b) { // 依學號
    return (*(Student*)a).id - (*(Student*)b).id;
}

int cmp2(const void* _a, const void* _b) { // 依姓名，次按學號
    Student a = *(Student*)_a, b = *(Student*)_b;
    int r = strcmp(a.name, b.name);
    return r ? r : a.id - b.id;
}

int cmp3(const void* _a, const void* _b) { // 依分數，次按學號
    Student a = *(Student*)_a, b = *(Student*)_b;
    return (a.score != b.score) ? a.score - b.score : a.id - b.id;
}

主程式流程

int main() {
    int N, C;
    scanf("%d %d", &N, &C);
    Student stu[N];
    for (int i = 0; i < N; ++i)
        scanf("%d %s %d", &stu[i].id, stu[i].name, &stu[i].score);

    int (*fp)(const void*, const void*);
    if (C == 1) fp = cmp1;
    else if (C == 2) fp = cmp2;
    else fp = cmp3;

    qsort(stu, N, sizeof(Student), fp);

    for (int i = 0; i < N; ++i)
        printf("%06d %s %d\n", stu[i].id, stu[i].name, stu[i].score);
    return 0;
}

複雜度分析

• 時間：O(N log N)，qsort 平均複雜度
• 空間：O(N) 儲存學生陣列

測試樣例

輸入 1（C=1）：

3 1
000007 James 85
000010 Amy 90
000001 Zoe 60

輸出 1：

000001 Zoe 60
000007 James 85
000010 Amy 90

輸入 2（C=2）：

4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98

輸出 2：

000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60

輸入 3（C=3）：

4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90

輸出 3：

000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90