C/C++ 學生成績多鍵值排序：快速排序失敗原因深度解析與標準庫替代方案

題目復盤

需對 n 名學生按 k 門課成績排名：總分降序 → 科目 1 降序 → 科目 2 降序 … → 學號升序，輸出前 10 名。

原代碼核心問題

1. 遞歸邊界條件錯誤：if(S.left>=S.left) return; 永真，導致無限遞歸棧溢出。
2. 分區邏輯缺陷：未正確處理多鍵值比較，僅按總分單鍵排序。
3. 數組下標越界風險：data[100000][2] 固定大小，實際 n 可能超限。
4. 輸入解析錯誤：scanf 格式字符串與樣例不匹配，導致讀取錯位。

正確比較器設計

struct Student {
    int id;
    vector<int> scores; // size = k
    int total() const { return accumulate(scores.begin(), scores.end(), 0); }
};

bool cmp(const Student& a, const Student& b) {
    if (a.total() != b.total()) return a.total() > b.total(); // 總分降序
    for (int i = 0; i < a.scores.size(); ++i) { // 依次比較各科
        if (a.scores[i] != b.scores[i]) return a.scores[i] > b.scores[i];
    }
    return a.id < b.id; // 學號升序
}

推薦實現：std::sort + 自定義比較器

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<Student> stu(n);
    for (int i = 0; i < n; ++i) {
        stu[i].id = i + 1;
        stu[i].scores.resize(k);
        for (int j = 0; j < k; ++j) cin >> stu[i].scores[j];
    }
    sort(stu.begin(), stu.end(), cmp);
    for (int i = 0; i < min(10, n); ++i) {
        cout << stu[i].id << (i == 9 || i == n-1 ? '\n' : ' ');
    }
    return 0;
}

為何不用手寫快排？

• std::sort 為 Introsort（快排+堆排+插排混合），平均 O(n log n)、最壞 O(n log n)，且經過高度優化。
• 手寫多鍵值快排極易出錯（穩定性、基準選取、尾遞歸優化），維護成本高。
• 面試/考試中，正確使用標準庫比手寫算法更能體現工程素養。

擴展：海量數據外部排序思路

若 n 達億級、內存不足，可採用歸併排序+臨時文件：將數據分塊讀入內存排序後寫入磁盤，再多路歸併輸出前 10 名。