1. Python 列表排序的基础方法
在学习 Python 的排序能力时，了解内置方法是第一步。sorted() 会返回一个新的排序后的列表，list.sort() 则就地对原列表进行排序；两者都具备稳定性，确保相等元素的相对顺序保持不变。时间复杂度为 O(n log n) 的通用排序性能在大多数数据集上都表现良好。
默认情况下，排序使用元素的自然顺序进行比较，例如数字按数值大小、字符串按字典序。若要自定义排序标准，可以传入 key 参数和可选的 reverse 参数，这会改变排序键和方向。Timsort 是 Python 的默认排序算法，结合稳定性和局部性优化，适合多数场景。
lst = [3, 1, 4, 1, 5, 9]
print(sorted(lst)) # [1, 1, 3, 4, 5, 9]
lst.sort()
print(lst) # [1, 1, 3, 4, 5, 9]
1.1 内置方法的行为要点
使用 sorted() 时，原列表不变，对比新生成的列表进行后续处理时非常方便。list.sort() 的就地排序则会修改原始数据，适合节省额外内存的场景。两者都是 稳定排序，这意味着当排序键相同时，前后元素的原始相对顺序会被保留。
下面的示例展示了两者的差异与简要语义：
# sorted 不改变原始 lst
lst = [5, 2, 7]
new_lst = sorted(lst)
print(lst) # [5, 2, 7]
print(new_lst) # [2, 5, 7]# list.sort 就地排序
lst.sort()
print(lst) # [2, 5, 7]
2. 自定义排序的核心：通过 key 参数提升排序能力
2.1 key 函数的工作原理
核心机制是将每个元素映射到一个排序键，然后按照这些键进行比较。使用 key 函数不会改变原始元素的结构，只是提供用于比较的中间值。此设计使得复杂的排序逻辑可以简化为键提取和标准的数值或字符串比较。稳定性同样适用于带有 key 的排序。
通过将耗时的计算移到 key() 的一次性执行，可以避免在比较阶段重复计算，从而提升性能。
data = ['apple', 'banana', 'pear']
# 根据字符串长度排序
print(sorted(data, key=len)) # ['pear', 'apple', 'banana']
2.2 使用 lambda 与常用工具函数
在 key 的实现中，lambda 表示一个简短的匿名函数，常用于快速定义排序键。对于更复杂的字段组合，可以使用 Python 的标准工具函数 operator.itemgetter 和 operator.attrgetter 来提取键。
下面的例子演示了以元组键进行多维排序：
data = [(2, 'b'), (1, 'a'), (2, 'a')]
print(sorted(data, key=lambda x: (x[0], x[1]))) # [(1, 'a'), (2, 'a'), (2, 'b')]from operator import itemgetter
print(sorted(data, key=itemgetter(0, 1)))
2.3 针对对象的属性排序：attrgetter
对于自定义对象，attrgetter 可以方便地按一个或多个属性排序。此方法保持了代码的清晰性，同时让排序逻辑与数据模型解耦。
from operator import attrgetterclass User:def __init__(self, name, age):self.name = nameself.age = ageusers = [User('Alice', 30), User('Bob', 25)]
sorted_by_age = sorted(users, key=attrgetter('age'))
print([u.name for u in sorted_by_age]) # ['Bob', 'Alice']
3. 稳定性与多字段排序技巧
3.1 多字段排序的简洁做法
多字段排序通常通过一个复合键来实现，即把要比较的各字段组合成一个键。以元组形式返回的键会按字典序逐一比较，达到多维排序的效果。元组比较在 Python 中天然支持。
这种方式在大量数据中仍然保持良好性能，因为排序的主要成本仍然来自比较次数，而键的生成通常较为轻量。
records = [{'name': 'Anna', 'score': 92},{'name': 'Ben', 'score': 92},{'name': 'Cara', 'score': 87},
]
sorted_by_score_name = sorted(records, key=lambda r: (r['score'], r['name']))
print([r['name'] for r in sorted_by_score_name]) # ['Cara', 'Anna', 'Ben']
3.2 稳定排序的含义与影响
Python 的排序算法是 稳定的，意味着当排序键相等时，前后元素的原始相对顺序保持不变。这在分段排序或多阶段排序中尤为重要。Timsort 的稳定性为复杂数据提供了可靠的行为。
以下示例直观展示稳定性：即使第一字段相同，第二字段的原始顺序也被保留。
data = [(1, 'a'), (1, 'b'), (0, 'z')]
print(sorted(data, key=lambda t: t[0]))
# [(0, 'z'), (1, 'a'), (1, 'b')]
3.3 自定义排序时的副作用与注意点
编写 key 函数时应尽量避免在其中进行耗时的全局计算。装饰-排序-解装饰（decorate-sort-undecorate）思想可以帮助理解：先对元素做键的预处理，再进行排序，最后还原为原始数据的过程。
data = ['banana', 'apple', 'pear']
pairs = [(len(s), s) for s in data] # decorate
pairs.sort() # sort by the first item in tuple
result = [s for _, s in pairs] # undecorate
print(result) # ['apple', 'pear', 'banana']
4. 装饰排序与性能优化
4.1 装饰排序的原理
装饰排序的核心在于把排序键和元素一起组织出来，先对包含键的“装饰体”进行排序，再提取出原始值。这种思路使得复杂的比较逻辑被转移到键的生成阶段，排序阶段只关注键的大小关系。
虽然 key 参数提供了相同的效果，但理解装饰排序有助于优化与调试，尤其在历史代码或需要对比较过程进行微调时。
data = ['banana', 'apple', 'pear']
pairs = [(len(s), s) for s in data] # decorate
pairs.sort() # sort by the first element (length)
result = [s for _, s in pairs] # undecorate
print(result) # ['pear', 'apple', 'banana'] or depending on lengths
4.2 使用 key 参数替代装饰排序的优点
在现代 Python 版本中，使用 key 参数通常比手动实现装饰排序更高效，因为排序实现会在内部预先计算键值并缓存以避免重复计算。
通过正确选择 key，可以获得接近手写装饰排序的灵活性，同时降低代码复杂度与内存峰值。
4.3 性能对比要点
一方面，key 的使用会让每个元素仅仅被计算一次键值，另一方面，排序本身仍然是 O(n log n) 的时间复杂度。对于耗时的键计算，预先缓存键值是显著的性能优化手段。
import timeitsetup = '''
lst = list(range(10000))
def heavy_key(x):return (x*x) % 997
'''
print(timeit.timeit('sorted(lst, key=heavy_key)', setup=setup, number=5))
print(timeit.timeit('sorted(lst, key=lambda x: (x*x) % 997)', setup=setup, number=5))
5. 实战场景与性能调优要点
5.1 大规模数据排序的策略
当处理大量数据时，内存与时间的权衡成为核心。优先选择就地排序以减少额外的内存开销，必要时也可用 sorted() 处理后再替换原数据。Timsort 的稳定性在数据部分有重复值的场景下尤为受益。
结合前述的 key 函数设计，可以把昂贵的计算提前完成，降低后续比较的成本。
# 大规模记录按年龄升序、再按姓名字母序排序
records = [{'name':'Anna','age':30}, {'name':'Ben','age':25}, {'name':'Cara','age':30}]
print(sorted(records, key=lambda r: (r['age'], r['name'])))
5.2 数据结构与排序的协同优化
尽量让排序的键提取尽可能轻量，避免在 key 函数中进行多次全局扫描或涉及 I/O。若数据结构允许，优先使用纯 Python 的元组、字典访问和标准字段，以减少解释器的负担。
5.3 真实场景下的注意点
在混合类型的列表中，确保排序键对所有元素具有可比性，避免运行时错误。对于自定义对象，attrgetter 与 itemgetter 为排序键提供了简洁且高效的解决方案。稳定性在多阶段排序中保持一致性，帮助你实现复杂的排序策略。
