Python 列表具有内置的 list.sort() 方法，该方法可就地修改列表。还有一个 sorted() 内置函数，可从迭代器构建新的排序列表。

因为 Python3 中 sorted() 和 list.sort() 放弃了类似 C++ 中的 cmp 写法，本文将展示官方推荐替代解决方案，以实现自定义的两个参数的比较函数，并详细分析了 cmp_to_key 函数实现原理。

python 自定义比较函数

排序基础

一个简单的升序排序非常容易：只需调用 sorted() 函数即可。它返回一个新的排序列表：

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

你也可以使用 list.sort() 方法。它就地修改列表（并返回 None 以避免混淆）。通常，它不如 sorted() 方便（如果你不需要原始列表，则效率会略高一些）。

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

另一个区别是 list.sort() 方法仅为列表定义。而 sorted() 函数接受任何可迭代的对象。

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

Key Functions

list.sort() 和 sorted() 都有一个 key 参数，用于指定在进行比较之前在每个列表元素上要调用的函数。例如，这是不区分大小写的字符串比较：

>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

key 参数的值应该是一个采用单个参数并返回用于排序目的的键的函数。 这种技术之所以快捷，是因为对于每个输入记录，key function 都只被调用一次。

一种常见的模式是使用某些对象的索引作为键来对复杂的对象进行排序。例如：

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

具有命名属性的对象也可以使用相同的技术。例如：

>>> class Student:
...     def __init__(self, name, grade, age):
...         self.name = name
...         self.grade = grade
...         self.age = age
...     def __repr__(self):
...         return repr((self.name, self.grade, self.age))

>>> student_objects = [
...     Student('john', 'A', 15),
...     Student('jane', 'B', 12),
...     Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age)   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

为什么取消 cmp 参数

所有 Py2.x 版本都支持 cmp 参数来处理用户指定的比较功能。

在 Py3.0 中，完全删除了 cmp 参数（这是简化和统一语言的较大工作的一部分，从而消除了丰富的比较与 __cmp__() 魔术方法之间的冲突）。

在 Py2.x 中使用 cmp 参数

Py2.x 中，sort 允许一个可选函数，可以进行比较。该函数应该接受两个参数进行比较，如果是小于等于的返回负值，如果相等则返回零，如果是大于等于的返回正值。例如，我们可以做：

>>> def numeric_compare(x, y):
...     return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)
[1, 2, 3, 4, 5]

或者，你可以通过以下方式反转比较顺序：

>>> def reverse_numeric(x, y):
...     return y - x
>>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric)
[5, 4, 3, 2, 1]

使用 cmp_to_key 函数实现自定义比较函数

当将代码从 Python 2.x 移植到 3.x 时，如果你有使用自定义比较功能的函数，需要将其转换为 Key function，我们可以使用 functools 提供的 cmp_to_key() 来实现：

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            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
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

要转换为 Key Function，只需包装旧的比较函数：

>>> from functools import cmp_to_key
>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]

在 Python 3.2 中，functools.cmp_to_key() 函数已添加到标准库的 functools 模块中。

理解 cmp_to_key 函数

如果你明白了 Key Function 的作用，那么再看 cmp_to_key 的代码就非常容易理解了。

cmp_to_key 接收一个比较函数作为内部类实例比较时执行的函数，并返回这个类。根据 key=com_to_key(mycmp) 可以知道最终作为 Key Function 的是一个类，这个类就是 cmp_to_key 返回的类 K。因为 Key Function 是作用在可迭代对象的每个元素上的，那么这个类又是怎么作用到每个元素的呢。

这里，你可能需要明确一点，Key Function 允许接受的来源不一定是函数，实际上它可以接受一切可调用对象，而类也是一个可调用对象。

据 "流畅的python" 中关于可调用对象的描述，类是 Python 数据模型文档列出的 7 种可调用对象中的一种：

调用类时会运行类的 __new__ 方法创建一个实例，然后运行 __init__ 方法，初始化实例，最后把实例返回给调用方。因为 Python 没有 new 运算符，所以调用类相当于调用函数。（通常，调用类会创建 那个类的实例，不过覆盖 __new__ 方法的话，也可能出现其他行为。）

到此，我们可以知道 cmp_to_key 函数返回的类作用到每个元素的结果了，这个类的作用结果就是：创建一个 K 类的实例，这个实例接收当前作用元素进行初始化，返回初始化后的实例。

在 K 类的实例间进行比较时，就会调用相应的特殊方法，如 < 将调用 __lt__ 方法，而 K 类实现的 __lt__ 将使用我们自己定义的函数进行比较。

References

https://docs.python.org/3/howto/sorting.html#sortinghowto