Python 3中怎么使用functools.cmp_to_key替代cmp函数

在 Python 3 中，内置的 sorted() 函数和列表的 list.sort() 方法完全移除了对 cmp 比较参数的支持，统一仅保留单参数映射的 key 函数。要复用原有的双参数比较逻辑或实现复杂的互比规则，最直接标准的方案是从内置模块导入工具函数：from functools import cmp_to_key，随后将原本返回 -1、0、1 的比较函数用其包装，并赋值给 key 参数即可。

一、为什么 Python 3 废弃了 cmp 参数

在 Python 2 时代，排序支持两种不同的自定义策略：基于两两对比的双参数函数 cmp(a, b)，以及基于单元素特征提取的单参数函数 key(x)。双参数 cmp 函数约定当 a < b 时返回负数，a == b 时返回 0，a > b 时返回正数。

这种机制虽然直观，但在排序算法（Python 使用的是 Timsort）执行过程中，每两两比较两个元素，就必须触发一次 Python 层的函数调用。若待排序序列长度为 $N$，则需要进行 $O(N \log N)$ 次高开销的解释器层函数调用。相比之下，key 机制为每个列表项仅调用一次映射函数（共 $N$ 次），随后直接复用提取出的键在底层 C 代码中进行极速比较，性能往往提升数倍乃至数十倍。

二、使用 cmp_to_key 的标准步骤

使用 cmp_to_key 进行迁移和重构非常直观，整个实现过程可以归纳为规范的四个步骤：

1. 编写或保留双参数比较函数

首先按照传统的比较语义定义比较函数。该函数接收两个参数 (a, b)：

• 若期望 a 排在 b 前面（即 a < b），返回负整数（通常为 -1）；
• 若两元素地位相等（a == b），返回 0；
• 若期望 a 排在 b 后面（即 a > b），返回正整数（通常为 1）。

2. 导入与调用包装

以下为一个基础整数列表逆序排序的具体示例：

from functools import cmp_to_key

# 1. 定义传统的比较函数
def custom_reverse_cmp(a, b):
    if a > b:
        return -1  # 期望较大的数排在前面
    elif a < b:
        return 1   # 较小的数排在后面
    return 0

numbers = [5, 2, 9, 1, 5, 6]

# 2. 通过 key=cmp_to_key(...) 进行排序
sorted_numbers = sorted(numbers, key=cmp_to_key(custom_reverse_cmp))

# 输出示例：[9, 6, 5, 5, 2, 1]
print("排序结果:", sorted_numbers)

三、cmp_to_key 的底层工作机制

不少初学者容易困惑：key 参数明明要求的是一个“接受单个参数并返回标量”的函数，为什么把 cmp_to_key(func) 传进去就能实现两两比较？

其实，cmp_to_key 并不是在排序引擎内部重新开启了双参数接口，而是使用了一个优雅的对象包装器类（Wrapper Class）设计模式。其内部创建了一个动态类 K，并将待比较的原始元素包装为 K(x) 实例。该类通过重写 Python 的富比较魔术方法（如 __lt__、__gt__、__eq__），在底层调用你提供的 cmp 函数。

用一段简化的 Python 等价伪代码来表示，其核心逻辑本质如下：

def cmp_to_key(my_cmp):
    class K:
        __slots__ = ['obj']
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return my_cmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return my_cmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return my_cmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return my_cmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return my_cmp(self.obj, other.obj) >= 0
    return K

理解了这一点，就能明白为什么 cmp_to_key 可以无缝嵌入任何标准 key= 接收端，同时也解释了为什么它会比纯原生 key 稍多一点包装与方法调用的开销。

四、经典实战场景：什么时候必须用 cmp_to_key

在大部分普通排序中，例如按对象的某个属性或多字段元组排序（如 key=lambda x: (x.age, -x.score)），完全不需要使用 cmp_to_key。然而，当排序权重依赖两个元素之间的相对拼接或相互运算时，无法为单个元素计算出一个绝对独立的 Key，此时 cmp_to_key 是最自然且优雅的解法。

案例：最大数字拼接（LeetCode 179 经典问题）

给定一组非负整数，重新排列它们的顺序使之拼接组成的数字最大。例如输入 [3, 30, 34, 5, 9]，输出应为 "9534330"。

在这个问题中，比较 3 和 30 的优劣，取决于字符串拼接结果："3" + "30" = "330" 大于 "30" + "3" = "303"，因此 3 应该排在 30 的前面。这种规则天然属于“两两互动比较”：

from functools import cmp_to_key

def compare_concatenation(a_str, b_str):
    # 如果 a + b 组合更大，说明 a 应当排在前面（即 a 相对更“小”/排在左边）
    comb1 = a_str + b_str
    comb2 = b_str + a_str
    
    if comb1 > comb2:
        return -1  # a 排在前
    elif comb1 < comb2:
        return 1   # b 排在前
    return 0

def largest_number(nums):
    # 转换为字符串列表
    str_nums = [str(n) for n in nums]
    
    # 使用 cmp_to_key 按照两两拼接规则排序
    str_nums.sort(key=cmp_to_key(compare_concatenation))
    
    # 特殊情况处理：全是0的情况拼接结果为 '0'
    result = "".join(str_nums)
    return "0" if result[0] == "0" else result

# 示例执行
sample_input = [3, 30, 34, 5, 9]
print("拼接最大数结果:", largest_number(sample_input))  # 输出示例：9534330

五、编写自定义比较函数的三大禁忌

在使用 cmp_to_key 时，必须保证自定义的比较函数满足严格弱序（Strict Weak Ordering）。如果不满足数学规律，排序结果可能出现不可预测的错乱，甚至在不同 Python 版本中表现不一致：

• 反对称性（Antisymmetry）：如果 cmp(a, b) < 0，那么必须有 cmp(b, a) > 0。切忌出现 cmp(a, b) 和 cmp(b, a) 同时返回负数或同时返回正数的情况。
• 传递性（Transitivity）：若 cmp(a, b) < 0 且 cmp(b, c) < 0，则必须保证 cmp(a, c) < 0。一旦存在环状关系（如剪刀石头布），Timsort 会产生未定义结果。
• 等价相容性：若 cmp(a, b) == 0 且 cmp(b, c) == 0，则 cmp(a, c) == 0 必须成立。

六、选型指南与方案总结

面对排序重构或新需求时，如何在原生 key 与 cmp_to_key 之间做出合理选择？以下决策流程给出了清晰的判断依据：

总结而言，functools.cmp_to_key 是 Python 标准库为兼顾现代键值排序体系与复杂两两比较逻辑之间所提供的“桥接器”。只要掌握定义规范的 -1/0/1 比较函数，并在 sorted() 中使用 key=cmp_to_key(your_cmp) 进行包裹，就能在 Python 3 中规范、安全地实现任意维度的自定义排序。