排序算法之：多条件排序（Multi-Criteria Sorting）的进阶应用：稳定性与性能优化

题目描述
给定一个包含多个属性的对象数组（例如学生记录，包含姓名、分数、年龄等），要求按照多个条件进行排序。例如：先按分数降序排列，分数相同的按年龄升序排列，年龄相同的按姓名字典序升序排列。需要保证排序的稳定性（即相同键值的元素相对顺序不变），并优化性能以避免多次全排序。

解题过程

1. 理解多条件排序的核心需求

多条件排序的本质是定义元素的优先级顺序。当两个元素的第一个比较条件相同时，需要根据第二个条件决定顺序，若第二个条件也相同，则继续比较第三个条件，依此类推。

关键点：

• 比较逻辑需按优先级依次判断条件。
• 稳定性要求：若所有比较条件均相同，原始相对顺序应保留。

2. 实现多条件比较器

以学生记录为例，定义比较规则：

1. 分数降序（高分在前） → 分数相等时进入下一条件；
2. 年龄升序（年轻在前） → 年龄相等时进入下一条件；
3. 姓名升序（字典序）。

比较函数伪代码（以升序为例，降序需调整比较符号）：

function compare(a, b):  
    if a.score != b.score:  
        return b.score - a.score  // 分数降序  
    else if a.age != b.age:  
        return a.age - b.age     // 年龄升序  
    else:  
        return a.name.compare(b.name)  // 姓名升序  

注意：若直接使用非稳定排序算法（如快速排序），相同键值的元素可能被打乱顺序。因此需选择稳定排序算法（如归并排序、TimSort）或通过额外处理保证稳定性。

3. 选择排序算法与稳定性保证

稳定排序算法：

• 归并排序（Merge Sort）
• 插入排序（Insertion Sort）
• 冒泡排序（Bubble Sort）
• TimSort（混合算法，Python/Java内置）

推荐方案：

• 对于大规模数据，优先使用归并排序或TimSort，时间复杂度为 O(N log N)，且天然稳定。
• 若语言内置排序函数（如Python的sorted、Java的Collections.sort）已优化且稳定，可直接利用其实现多条件比较器。

示例（Python）：

students = [  
    {"name": "Alice", "score": 90, "age": 20},  
    {"name": "Bob", "score": 90, "age": 19},  
    {"name": "Charlie", "score": 85, "age": 21}  
]  

# 按分数降序、年龄升序、姓名升序排序  
sorted_students = sorted(students, key=lambda x: (-x["score"], x["age"], x["name"]))  

原理：

• key参数生成元组(-score, age, name)，元组按字典序比较（先比较第一个元素，再比较第二个，依此类推）。
• 负数技巧实现降序（例如-score使高分对应的元组更小，从而排在前）。

4. 性能优化策略

避免多次排序：

• 错误做法：先按姓名排序，再按年龄排序，最后按分数排序（后一次排序会破坏前一次的结果）。
• 正确做法：一次性生成所有比较条件的复合键（如元组），通过单次排序完成。

优化比较操作：

• 若某些条件计算成本高（如字符串处理），可预计算并缓存比较键（如上述元组），避免重复计算。
• 对于大规模数据，比较函数应尽量简单，减少分支预测失败。

5. 处理动态条件与扩展性

若排序条件需动态指定（如用户选择不同优先级），可设计通用比较器工厂：

def multi_field_comparator(fields):  
    """  
    fields: 列表，每个元素为(字段名, 升序True/降序False)  
    """  
    def comparator(obj):  
        key = []  
        for field, ascending in fields:  
            value = obj[field]  
            key.append(value if ascending else -value)  
        return tuple(key)  
    return comparator  

# 使用示例  
comparator = multi_field_comparator([("score", False), ("age", True), ("name", True)])  
sorted_students = sorted(students, key=comparator)  

6. 总结

• 多条件排序通过复合键比较实现优先级逻辑。
• 稳定性需由算法本身（如归并排序）或额外处理（如添加原始索引作为最后比较条件）保证。
• 性能优化关键在于单次排序完成所有条件比较，并预计算昂贵操作。
• 实际开发中优先使用语言内置的稳定排序函数，避免重复造轮子。