Python中两种自定义排序比较函数行为差异原因探究

我们的需求是将字符串数组排序，使得拼接后的结果是字典序最大的字符串，通过functools.cmp_to_key自定义比较逻辑，但两种比较函数的结果差异很大，第一种无法得到正确结果，核心问题出在比较函数的返回值类型上。

第一种比较函数及输出 #

from functools import cmp_to_key
def compare(a,b):
    print(a,b, a+b,b+a,a+b>b+a) 
    return (a+b)>(b+a) # 返回布尔值

def sortArr(ls):
    ls = sorted(ls,key =cmp_to_key(compare),reverse=True)
    return "".join(ls)

ls = ["8","81","82","829"]
print(sortArr(ls))

输出：

82 829 82829 82982 False
81 82 8182 8281 False
8 81 881 818 True
88182829

第二种比较函数及输出 #

from functools import cmp_to_key
def compare(a,b):
    print(a,b, a+b,b+a,a+b>b+a)
    return int(a+b) -int(b+a) # 返回整数

def sortArr(ls):
    ls = sorted(ls,key =cmp_to_key(compare),reverse=True)
    return "".join(ls)

ls = ["8","81","82","829"]
print(sortArr(ls))

输出：

82 829 82829 82982 False
81 82 8182 8281 False
8 81 881 818 True
8 82 882 828 True
8 829 8829 8298 True
88298281

问题根源：cmp_to_key对返回值的严格要求 #

cmp_to_key规定传入的比较函数必须返回整数，判定规则为：

• 返回负数：a优先级更高，应排在b前面
• 返回正数：b优先级更高，应排在a前面
• 返回0：a和b排序优先级相同

第一种比较函数返回的是布尔值True/False，在Python中会被隐式转为1和0。这就导致：
当a+b <= b+a时，函数返回False（即0），sorted会判定a和b优先级相等，跳过后续必要的交叉比较（比如示例中8与82、8与829的比较完全没触发），最终排序逻辑缺失，得到错误结果。

而第二种比较函数返回整数差值：

• 当a+b字典序更大时，返回正数，配合reverse=True会把a放在前面
• 当b+a字典序更大时，返回负数，配合reverse=True会把b放在前面
  完全符合cmp_to_key的要求，排序算法能完成所有必要的比较，最终得到正确的字典序最大字符串。

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