Python3自定义排序

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

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

---

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

$1 自定义排序

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

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

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

代码: 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 中这参数 cmp 取消了，但是还是可以通过 key 参数实现自定义排序。调用时，参数 key 可以指定一个带参数的函数 mykey，mykey 返回 list 元素用于比较的 key，这个 key 实现了 __lt__ 等特殊方法。

代码: python3 风格自定义比较函数

def mykey(x, y):
    return x.key

l.sort(key=mykey)

通过 functools.cmp_to_key(mycmp) 可以将 python2 的 mycmp 变成 mykey。

l.sort(key=cmp_to_key(mycmp))

代码: cmp_to_key 的实现

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

$2 题目

506. 相对名次

问题

给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（”Gold Medal”, “Silver Medal”, “Bronze Medal”）。

(注：分数越高的选手，排名越靠前。)

代码

• 定义 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

• 直接定义 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

---