本文整理自 HowTo/Sorting - Python Wiki，如有不妥之处，请翻阅英文原文。
Python 内置的 sort() 方法可以实现对列表的原地排序功能。内置的 sorted() 函数则不会修改原列表，而是生成一个经过排序的新列表。
下面总结一些常用的排序方法。
基本排序
最简单的方法就是使用 sorted() 函数，它将返回一个经过排序的新列表：
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]
你也可以使用 list.sort() 方法， 但是它会修改原列表，所以一般使用 sorted()。如果你不再需要原始列表的话，用用 list.sort() 也无妨。
>>> 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 函数
从 Python 2.4 开始， list.sort() 及 sorted() 增加了一个 key 参数，该参数接受一个函数作为它的值，可以通过那个函数定义排序应该遵循的规则。
比如，对字符串做不区分大小写的排序：
>>> sorted("This is a test string from Andrew".split(), key=str.lower)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
>>> # 对照
>>> sorted("This is a test string from Andrew".split())
['Andrew', 'This', 'a', 'from', 'is', 'string', 'test']
key 参数的值必须是个函数，该函数有一个参数（列表元素）并且返回一个用来排序的 key（按这个 key 进行排序）。
一般通过使用对象的某个索引作为 key 的值来对复杂对象进行排序。比如对一个多维数组进行排序：
>>> student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
# 按列表元素（元组）的第3个值排序
>>> 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),
]
# 按 age 属性的值排序
>>> sorted(student_objects, key=lambda student: student.age) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Operator 模块函数
由于 key 参数比较常用，所以 Python 内置了一些用来简单、快速生成相关函数的方法。 operator 模块 提供了 itemgetter，attrgetter， 以及从 Python 2.6 开始提供的 methodcaller 函数。
使用这些函数，上面的例子将变得更简单、更快速：
>>> from operator import itemgetter, attrgetter
>>> student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
>>> sorted(student_tuples, key=itemgetter(2)) # 按元素索引排序
[('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=attrgetter('age')) # 按对象属性排序
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
通过 operator 模块提供的函数还可以实现多重排序的功能。比如，先按 grade 排序再按 age 排序：
>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
methodcaller 函数可以让元素调用一个方法，然后按方法的返回值进行排序：
>>> words = ['b', 'a', 'abase', 'alfalfa']
>>> sorted(words, key=methodcaller('count', 'a')) # word.count('a')
['b', 'a', 'abase', 'alfalfa']
# 等价于
>>> sorted(words, key=lambda word: word.count('a'))
['b', 'a', 'abase', 'alfalfa']
>>>
升序和降序
list.sort() 和 sorted() 都接受一个布尔类型的 reverse 参数。这个参数用来标记是否使用降序排序。比如获取按 age 降序排序的 student 数据：
>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
平衡（Stability）排序和复杂排序
从 Python 2.2 开始，排序将保证能够 stable。 这意味着当多个记录拥有相同的 key 时，它们的原始顺序将被保留。
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
这里有两条记录都包含 'blue' 并且原列表中 ('blue', 1) 排在 ('blue', 2) 之前，排序后这个顺序依旧被保留。
这个非常有用的特性可以用来实现包含多重排序（一会升序，一会降序）的复杂排序。比如，目标是实现 student 数据先以 grade 降序排序再以 age 升序排序：
>>> 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),
]
>>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key
>>> s
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Python 使用的 Timsort 排序算法能够高效的实现多重排序。
以前的实现方式(Decorate-Sort-Undecorate)
Python 2.4 之前的惯用方法之一是使用 Decorate-Sort-Undecorate，比如将 student 数据按 grade 排序：
>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated] # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
这种方法的另一个名字是 Schwartzian transform，有兴趣的可以去了解一下。
以前的实现方式(使用 cmp 参数)
Python 2.4 之前惯用的另一种方法是使用 cmp 参数：
>>> 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]
Python 3 不再支持 cmp 参数，那么如果转换之前的程序呢？可以使用下面的代码：
def cmp_to_key(mycmp):
'Convert a cmp= function into a key= function'
class K(object):
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
用法：
>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric))
[5, 4, 3, 2, 1]
在 Python 2.7 中，cmp_to_key() 工具已经被内置到 functools 模块中。
其他
-
对于本地化排序，可以使用 locale.strxfrm() 作为 key 函数或使用 locale.strcoll() 作为比较函数。
-
reverse参数依然能够保存排序的稳定性（比如，拥有相同记录的 keys 依旧保留了原来的顺序），有趣的是，就算是不使用该参数也可以通过使用两次reversed函数来实现这种效果：>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data))))
-
如果想给类排序的话，只需添加相关的比较方法：
>>> Student.__eq__ = lambda self, other: self.age == other.age >>> Student.__ne__ = lambda self, other: self.age != other.age >>> Student.__lt__ = lambda self, other: self.age < other.age >>> Student.__le__ = lambda self, other: self.age <= other.age >>> Student.__gt__ = lambda self, other: self.age > other.age >>> Student.__ge__ = lambda self, other: self.age >= other.age >>> sorted(student_objects) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
一般情况下，只需定义上面6个比较操作就可以了。functools.total_ordering 类装饰器可以很方便就实现这个需求。
-
key 函数也可以不访问要排序对象的相关数据，访问外部资源也是可以的。比如，学生成绩存储在一个字典中，这个字典可以用来对学生名字进行排序：
>>> students = ['dave', 'john', 'jane'] >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'} >>> sorted(students, key=newgrades.__getitem__) ['jane', 'dave', 'john']
Comments