用途:帮助在 Python 中为排序类问题选择正确的做法,避免不必要的自定义实现。
主要能力与规则: Python 内置的 sorted() 与 list.sort() 即 Timsort,复杂度 O(n log n) 且稳定,在绝大多数情况下都应优先使用。自定义排序顺序用 key= 参数。取前 k 大或前 k 小元素时,应使用 heapq.nlargest/nsmallest,复杂度 O(n log k),而不是对整个数组排序。若只需第 k 个元素,可考虑 quickselect 或 statistics.median。计数排序、基数排序仅在数值为有界整数时才有帮助。当需求为“先按 X 再按 Y”排序时,使用元组键,例如 key=lambda x: (x.a, x.b)。若要仅对某一字段反向排序,可对该字段取负,或使用 functools.cmp_to_key。
复杂度参考:Timsort 为 O(n log n);heapq.nlargest/nsmallest 为 O(n log k)。
示例思路:“取前 3 个分数”用 heapq.nlargest(3, scores),复杂度 O(n log 3);“先按姓名再按年龄排序”用 sorted(items, key=lambda x: (x.name, x.age))。
限制:该技能强调始终优先内置排序,除非题目明确要求,否则不要自行实现排序算法。
适用场景:数组排序、top-k 查询、多字段排序及有界整数排序等编程问题。