Python3自定义排序：直接定义键函数，或先定义比较函数再转换为键函数

摘要: Python 3 中如何实现自定义排序

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

自定义排序是算法中很常见的一个操作，参考自定义排序。

$1 自定义排序

比较函数：Python2 风格

在 Python2 中，sort 和 sorted 可以通过参数 cmp 指定排序规则。

# python list 排序接口，直接在本地排序
list.sort(cmp=None, key=None, reverse=False) # Python2
list.sort(key=None, reverse=False)           # Python3

其中 python2 的排序规则一般写成比较函数(或者可调用对象)。

def mycmp(x, y):
    if x.key < y.key:
        return -1
    elif x.key > y.key:
        return 1
    else:
        return 0

l.sort(cmp=mycmp)

键函数: python3 风格

Python3 中参数 cmp 取消了，但是还是可以通过 key 参数实现自定义排序。调用时，参数 key 可以指定一个带参数的键函数 mykey，mykey 返回 list 元素用于比较的 key，这个 key 实现了 __lt__ 等特殊方法。

下面的例子中，mykey 是键函数，x 为 list 元素，键函数返回该元素用于比较的 key，也就是 x.key，而 x.key 是需要带有 __lt__ 等方法的。

def mykey(x):
    return x.key

l.sort(key=mykey)

cmp_to_key：比较函数转键函数

通过 functools.cmp_to_key(mycmp) 可以将 python2 的 mycmp 变成 mykey。代码如下：

l.sort(key=cmp_to_key(mycmp))

cmp_to_key 的实现

cmp_to_key 将比较函数转换为键函数。也就是键函数中的 __lt__ 等方法依据比较函数 mycmp 来实现。

大致的代码如下，其中 obj 代表一个 list 元素，返回的类 K 就是用于比较的键（事实上就可以理解为 obj 本身，只是给它加上了 __lt__ 等函数，所以可以理解 K 是 obj 的一个 Wrapper），其中的 __lt__ 是根据 mycmp 函数定义的：

def cmp_to_key(mycmp):
    """Convert a cmp= function into a key= function"""
    class K(object):
        __slots__ = ['obj']
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        __hash__ = None
    return K

这里的 __slots__ 是一个类属性，它用于限制实例属性的数量，从而节省内存。当你在类定义中使用 __slots__ 时，即可明确指定该类实例将具有的属性列表。

总结

总结一下，Python3 中 sort 函数对列表 l 排序，列表元素 x 可能没有 __lt__，这样 l 本身就不能排序；也可能 x 有 __lt__ 但是不是我们想要的逻辑。此时想要给 l 排序，一个最直接的办法是给 x 对象自定义一个 __lt__，这样 x 本身就可以支持按给定逻辑排序。

也可以通过给 sort 函数的 key 参数传递一个键函数的方式来做 key 参数接收一个可调用对象 mykey。mykey 在调用时接收一个参数 x 也就是 list 中的元素（这个元素 x 可能没有 __lt__，或者有 __lt__ 但不是我们想要的逻辑。）。mykey(x) 返回一个将 x 包装后的对象，代表用于比较 list 元素的键，而这个所谓的键其实就是 x 本身，只是给他增加了 __lt__ 等函数。所以其实质还是相当于给 x 对象自定义了 __lt__。

对于简单的情况，例如用于比较 list 元素的键就是元素的某个属性，且该属性是 int 等基本类型，自带了 __lt__，那么写法就很简单，参考前面【键函数：Python3 风格】这一小节的代码。

如果复杂情况，比如比较 list 元素时涉及到多个属性，或者某个属性没有自带 __lt__ 需要自己实现。那么可以先将比较的逻辑写在比较函数 mycmp 中，然后通过 cmp_to_key 转换为一个类包装器，作为 mykey。

---

$2 题目：506. 相对名次

给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。

运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：

• 名次第 1 的运动员获金牌 “Gold Medal” 。
• 名次第 2 的运动员获银牌 “Silver Medal” 。
• 名次第 3 的运动员获铜牌 “Bronze Medal” 。
• 从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 “x”）。

使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

提示：

n == score.length
1 <= n <= 1e4
0 <= score[i] <= 1e6
score 中的所有值 互不相同

示例 1：
输入：score = [5,4,3,2,1]
输出：[“Gold Medal”,”Silver Medal”,”Bronze Medal”,”4”,”5”]
解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。

示例 2：
输入：score = [10,3,8,9,4]
输出：[“Gold Medal”,”5”,”Bronze Medal”,”Silver Medal”,”4”]
解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。

代码(Python)，先定义比较函数，再转换为键函数

• 定义 python2 风格的比较函数，再通过 functools.cmp_to_key 转换为 python3 的提取 key 的键函数。

from functools import cmp_to_key

class Cmp:
    def __init__(self, nums):
        self.nums = nums

    def __call__(self, i, j):
        if self.nums[i] > self.nums[j]:
            return -1
        if self.nums[i] < self.nums[j]:
            return 1
        return 0


class Solution:
    def findRelativeRanks(self, nums: List[int]) -> List[str]:
        n = len(nums)
        indexes = [i for i in range(n)]
        mycmp = Cmp(nums)
        indexes.sort(key=cmp_to_key(mycmp))
        result = ["" for _ in range(n)]
        for i, idx in enumerate(indexes):
            if i == 0:
                result[idx] = "Gold Medal"
            elif i == 1:
                result[idx] = "Silver Medal"
            elif i == 2:
                result[idx] = "Bronze Medal"
            else:
                result[idx] = str(i + 1)
        return result

代码(Python)，直接定义键函数

• 直接定义 python3 的提取 key 的函数。

class Key:
    def __init__(self, nums):
        self.nums = nums

    def __call__(self, i):
        return self.nums[i]


class Solution:
    def findRelativeRanks(self, nums: List[int]) -> List[str]:
        n = len(nums)
        indexes = [i for i in range(n)]
        mykey = Key(nums)
        indexes.sort(key=mykey, reverse=True)
        result = ["" for _ in range(n)]
        for i, idx in enumerate(indexes):
            if i == 0:
                result[idx] = "Gold Medal"
            elif i == 1:
                result[idx] = "Silver Medal"
            elif i == 2:
                result[idx] = "Bronze Medal"
            else:
                result[idx] = str(i + 1)
        return result

---