cmp_to_key()工作原理与时间复杂度解析，含sorted拼接最大数场景

一、cmp_to_key()的工作原理 #

cmp_to_key()是Python标准库functools中的工具函数，核心作用是将自定义的二元比较函数转换为sorted()可接受的key函数：

• 自定义比较函数需要接受两个参数x和y，返回负数、零、正数分别表示x < y、x == y、x > y；
• cmp_to_key()会把列表中的每个元素包装成特殊的代理对象，当sorted()需要比较两个元素时，会自动调用你传入的自定义比较函数判断顺序，而非使用元素自身的默认比较逻辑。

拿你的代码举例：

from functools import cmp_to_key
a = [3,30,34,5,9]
b = sorted(map(str,a), key=cmp_to_key(lambda x,y: int(y+x) - int(x+y)))
# 输出: ['9', '5', '34', '3', '30']

这里的lambda函数定义了自定义比较逻辑：通过对比y+x和x+y的数值大小，返回差值让sorted()按照拼接后数值从大到小的顺序排列元素。

二、时间复杂度分析 #

1. 核心结论：不会变成O(n²)或O(n³ log n) #

Python的sorted()底层使用Timsort算法，本身的时间复杂度是O(n log n)——这个复杂度由排序过程中的比较次数决定，Timsort的比较次数始终是O(n log n)级别，和key函数无关。

2. cmp_to_key()的实际影响 #

cmp_to_key()并没有改变排序的比较次数，只是改变了单次比较的开销：

• 使用默认key时，单次比较是O(1)操作；
• 使用cmp_to_key()时，单次比较的开销取决于自定义比较函数。你的例子中，比较逻辑是固定长度的字符串拼接+转整数，属于O(1)的常数时间操作，因此整体时间复杂度仍然是O(n log n)。

3. 极端场景的开销变化 #

如果元素是长度与n相关的超长字符串，单次比较的开销会变成O(k)（k为字符串长度），此时整体时间复杂度变为O(k·n log n)，但这也远达不到O(n³ log n)——只有当单次比较开销达到O(n²)才会出现后者，你的场景完全不存在这种情况。

4. 为什么不会是O(n²) #

O(n²)是冒泡排序这类简单排序算法的比较次数，但Pythonsorted()用的是高效的Timsort，比较次数始终是O(n log n)，cmp_to_key()仅替换比较逻辑，不会增加比较次数，因此不会出现O(n²)的时间复杂度。

内容的提问来源于stack exchange，提问作者Mr.Bagel