Sicily 1351 Multi-key Sorting 多關鍵字排序詳解

Sicily 1351：Multi-key Sorting 中的 "Sorting" 含義

Sorting（排序） 在計算機科學中指將一組數據按照特定順序（升序/降序/自定義比較規則）重新排列的操作。Multi-key Sorting（多關鍵字排序） 則是當單個關鍵字無法唯一確定順序時，按優先級依次使用多個關鍵字進行比較排序。

核心概念

• 主關鍵字：首要比較依據（如姓氏拼音）。
• 次關鍵字：主關鍵字相等時啟用（如名字拼音）。
• 穩定性：若採用穩定排序算法（如歸併排序），可從最低優先級關鍵字開始依次排序，最終得到正確結果；若用不穩定排序（如快速排序），需自定義比較函數一次性完成多關鍵字比較。

典型應用場景

// 學生記錄：按「年級升序」→「班級升序」→「姓名拼音升序」
struct Student { int grade, class; string name; };
bool cmp(const Student& a, const Student& b) {
    if(a.grade != b.grade) return a.grade < b.grade;
    if(a.class != b.class) return a.class < b.class;
    return a.name < b.name; // 字典序比較
}
sort(students.begin(), students.end(), cmp);

Sicily 1351 具體題意

該題通常給定多組數據，每組包含多條記錄及多個排序關鍵字（含升/降序要求），要求輸出排序後的記錄。解題關鍵在於正確解析輸入格式、構建多級比較邏輯、處理大數據量下的性能（建議用 stable_sort 多輪排序或自定義 operator< 配合 sort）。

一言以蔽之：Sorting 即「排序」，Multi-key Sorting 即「多關鍵字排序」，核心是定義清晰的多級比較規則並選擇合適算法實現。