先看一个函数：

sorted(
    ...,
    key=lambda x: x[1],   
    reverse=True           
)

sorted(…)：Python 的内置排序函数。
key=lambda x: x[1]：这是排序的规则。lambda x: x[1] 是一个匿名函数，表示在比较元组时，只提取元组中的第二个元素（即索引为 1 ）作为排序依据。

sorted() 是 Python 中最常用、最强大的内置函数之一。它的核心功能是：接收一个可迭代对象（如列表、元组等），并返回一个全新的、排好序的列表。

它的完整语法如下：
sorted(iterable, *, key=None, reverse=False)

下面为你详细拆解它的三个核心参数：

iterable（可迭代对象）—— 要排序的“原材料”
这是必填参数。它可以是任何能逐个取出元素的容器，比如列表（List）、元组（Tuple）、字典（Dictionary）等。
注意：sorted() 不会修改你原来的数据，而是生成并返回一个全新的列表。

key（排序规则）—— 排序的“裁判”
这是可选参数。它接收一个函数，用来指定排序时比较的依据。
如果不写 key，Python 会按默认规则排序（数字按大小，字符串按首字母顺序）。
如果写了 key，Python 会先把列表中的每个元素都放进这个函数里算出一个结果，然后只根据这个结果来排序。例如：key=len 表示按字符串的长度排序；key=lambda x: x[1] 表示按元组的第二个元素排序。

reverse（排序方向）—— 决定“正序”还是“倒序”
这也是可选参数。它只接受布尔值（True 或 False）。
reverse=False（默认）：升序排列（从小到大，A-Z）。
reverse=True：降序排列（从大到小，Z-A）。
本篇重点讲一下这里的key：它在 Python 的底层实现中，它被称为 DSU 模式（Decorate-Sort-Undecorate，装饰-排序-去装饰）。

一、DSU 模式原理

当你给 sorted() 提供 key 参数时，Python 并不是在每次比较两个元素时去调用这个函数（那样效率太低了），而是遵循以下三个步骤：

Decorate（装饰）：Python 会遍历原始列表，对每个元素调用一次 key 函数，生成一个“排序键（Sort Key）”。然后在内存中把原始元素和这个排序键绑定在一起，形成一个内部元组：(排序键, 原始元素)。
Sort（排序）：Python 使用极其高效的 Timsort 算法，直接比较这些新生成的“排序键”来进行排序。因为排序键通常是简单的数字或字符串，所以比较速度非常快。
Undecorate（去装饰）：排序完成后，Python 会丢弃掉那些用来比较的“排序键”，只把原始的“原始元素”按照排好的顺序提取出来，返回给你。

举个例子：
假设 nums = [10, 2]，key=str（按字符串排序）。
装饰：生成内部列表 [(‘10’, 10), (‘2’, 2)]
排序：比较 ‘10’ 和 ‘2’，因为字符串 ‘1’ 在 ‘2’ 前面，所以 ‘10’ 排在前面。
去装饰：返回 [10, 2]（虽然数字上 2 更小，但按字符串字典序 10 在前面）。

二、sorted(key=…) 内部DSU完整流程

注意：Python 的 sorted(iterable, key=func) 在 CPython 内部自动执行 DSU（Schwartzian transform），不需要你手动 zip 打包。
DSU三步：Decorate(装饰) → Sort(排序) → Undecorate(去装饰)

伪代码描述 CPython 内部行为：

def sorted(iterable, key=None, reverse=False):
    # -------- Decorate【装饰】 --------
    # 对每一个元素，调用key函数一次，生成元组 (key_result, original_item)
    decorated = [ (key(x), x)  for x in iterable ]

    # -------- Sort【排序】 --------
    # 对装饰后的元组列表排序；元组比较优先对比第0项也就是key值
    decorated.sort(reverse=reverse)

    # -------- Undecorate【去装饰】 --------
    # 丢弃key，只把原始元素提取出来返回
    result = [ orig for (k, orig) in decorated ]
    return result

关键特性

1. 每个元素的 key(x) 只会被调用1次，总共 N 次调用，而不是 O(N log N)次。

如果没有DSU，直接在比较的时候计算key，每一次两两比较都重新算key，性能灾难。

2. 当多个元素的 key 值相等时，元组会继续比较第二个元素（原始对象），这保证了Python排序是稳定排序。

对比：手动DSU 和 key参数版本

输入：按字符串长度排序

data = ["apple", "cat", "banana", "dog"]

# ① 手动手写完整DSU
dec = [(len(s), s) for s in data]
dec_sorted = sorted(dec)
res1 = [v for k, v in dec_sorted]

# ② 使用key参数，内部自动DSU（等价上面，更简洁）
res2 = sorted(data, key=lambda s: len(s))

print(res1 == res2) # True

三、演示例：key函数只执行N次（DSU缓存效果）

我们写带打印的key函数，观察调用次数：

def my_key(s):
    print(f"调用my_key，输入={s}")
    return len(s)

data = ["apple", "cat", "banana", "dog"]
res = sorted(data, key=my_key)

输出：

调用my_key，输入=apple
调用my_key，输入=cat
调用my_key，输入=banana
调用my_key，输入=dog

四、Python中哪些内置/库函数拥有这套「预计算key、缓存key」DSU机制？

⚠️区分两类：

• A类：内部做Schwartzian变换，预计算并缓存key（DSU机制）
• B类：只接收比较函数cmp，没有key缓存，没有DSU

✅ 拥有DSU（key参数，预计算每个元素的key一次）

Python 中几乎所有涉及“排序”或“找极值”的内置函数，都完美支持这个 key 规则：

list.sort()：列表的自带排序方法，行为和 sorted() 完全一样，只是它直接在原列表上修改（原地排序）。
min() 和 max()：求最小值和最大值。
例如：min([10, 2, -5], key=abs)。它会先用 abs 算出绝对值 [10, 2, 5]，然后找出绝对值最小的那个原始数字，返回 2。

1. sorted() 内置函数
   全局内置函数，返回新列表，完整DSU。

2. list.sort() 实例方法

lst.sort(key=..., reverse=...)

原地排序，内部同样执行DSU；和sorted逻辑几乎一样，只是不返回新列表，修改自身。

sorted() → 先生成拷贝再内部调用 .sort()。

示例：

arr = ["zz", "a", "bbbb"]
arr.sort(key=len)
print(arr)

第三方库

• Pandas：DataFrame.sort_values()
df.sort_values(by="col")，底层是C实现，会提取排序键做一次提取，属于类似DSU思想，但不是Python语言层面的Schwartzian变换。

import pandas as pd
df = pd.DataFrame({"name":["a","bb","ccc"]})
df.sort_values(by="name")