Python中sorted()函数如何通过自定义key参数实现排序？

你的猜想是对的，Python的sorted()和列表自带的list.sort()处理key参数时，采用的是**装饰-排序-去装饰（Decorate-Sort-Undecorate, DSU）**模式，确实会临时存储所有元素对应的排序键，不会在排序比较阶段反复调用key函数。

你写的测试代码如下：

def sorthelper(x):
     return x[1]

ls=[('data2',1),('data1',3),('data3',2)]

print(sorted(ls,key=sorthelper))

完整执行流程分为3步：

• 装饰阶段
  排序启动后会首先遍历一次待排序列表的所有元素，对每个元素仅调用一次传入的key函数，生成对应的排序键，最终组装成形如(排序键, 原始元素, 原始索引)的中间元组列表。
  额外存储原始索引是为了保证排序稳定性：当两个元素的排序键完全相等时，会直接按照原始索引的先后顺序排列，不会打乱同键元素在原列表中的相对位置。
  对应你给出的示例，这一步生成的中间列表为：

  [(1, ('data2', 1), 0), (3, ('data1', 3), 1), (2, ('data3', 2), 2)]
  

  这个设计的核心优势是规避重复计算：不管排序过程中发生多少次元素比较，key函数的总调用次数永远等于待排序元素的总数，哪怕key函数逻辑很复杂，也不会带来额外的性能损耗。
• 排序阶段
  Python内置排序用的是Timsort算法，这一步直接对上面生成的中间元组列表做排序，比较时优先对比元组第一个位置的排序键，键相等时对比第三个位置的原始索引保序，全程不会再次调用key函数，也不会直接对比原始元素。
  你的示例排序完成后的中间列表为：

  [(1, ('data2', 1), 0), (2, ('data3', 2), 2), (3, ('data1', 3), 1)]
  

• 去装饰阶段
  排序完成后，遍历排好序的中间元组列表，把每个元组里存储的原始元素提取出来，按顺序拼成最终的结果列表返回，所有临时生成的排序键、中间元组都会在排序结束后被回收。
  最终你得到的输出就是[('data2', 1), ('data3', 2), ('data1', 3)]，和实际运行结果一致。

你可以自己做个简单验证：给key函数加打印逻辑看调用次数，比如把示例里的sorthelper改成：

def sorthelper(x):
    print(f"key函数被调用，处理元素：{x}")
    return x[1]

运行后你会看到打印语句刚好执行3次，和列表元素总数一致，不会因为排序比较出现更多次调用。

内容的提问来源于stack exchange，提问作者novice