Python如何基于两元素自定义比较规则实现列表排序

Python 3 原生的list.sort()和sorted()的key参数仅支持接收单参数函数，无法同时访问参与比较的两个元素，这类需要判断两个元素双向关联关系的排序需求，可以使用标准库functools模块中的cmp_to_key工具实现。

核心实现规则 #

cmp_to_key可以将自定义的双参数比较函数转换为排序兼容的key对象，自定义比较函数需要遵循固定返回规则：

• 若参数a应该排在b之前，返回负整数（常用-1）
• 若参数a应该排在b之后，返回正整数（常用1）
• 若两个元素排序优先级相等，返回0

排序时reverse参数可以正常使用，不需要修改比较函数内部逻辑。

适配示例代码 #

针对你给出的can_eat判断逻辑，实现代码如下：

from functools import cmp_to_key

class Apple:
    def can_eat(self, other):
        return False


class Human:
    def can_eat(self, other):
        # 示例逻辑：人可以吃人和苹果
        if isinstance(other, Human):
            return True
        return isinstance(other, Apple)

class Thing:
    def can_eat(self, other):
        return False


def compare(a, b):
    # 正向排序规则：如果a满足对b的can_eat关系，a排前面
    if a.can_eat(b):
        return -1
    if b.can_eat(a):
        return 1
    return 0


apple = Apple()
human = Human()

things = [apple, human, apple]
# 正向排序：human在前，apple在后
things.sort(key=cmp_to_key(compare))
print([type(i).__name__ for i in things])  # 输出: ['Human', 'Apple', 'Apple']

# 反向排序：apple在前，human在后
things.sort(key=cmp_to_key(compare), reverse=True)
print([type(i).__name__ for i in things])  # 输出: ['Apple', 'Apple', 'Human']

如果排序逻辑比较简单，也可以直接写成lambda形式，不需要单独定义函数：

things.sort(key=cmp_to_key(lambda a, b: -1 if a.can_eat(b) else 1 if b.can_eat(a) else 0))

注意事项 #

• 自定义的比较关系需要满足传递性（即如果a排在b前、b排在c前，那么a必须排在c前），否则基于Timsort的Python排序可能返回不符合预期的结果。
• 单参数key的排序性能比cmp_to_key高，如果能把两元素的关联关系转换成每个元素独立的固定权重值，优先使用key参数；只有必须依赖两个元素双向判断的场景，再使用cmp_to_key方案。

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