Python集合有一个内置的方法list.sort()用来对集合进行排序，它会修改集合本身。还有一个内建的函数sorted()，它可以从一个迭代器创建一个新的排序集合，这意味着它不会修改原来的集合。
这本文中，我们探索使用Python排序数据的各种技术。
基本的排序
对集合进行升序排序是非常简单的一件事情，只需要调用函数sorted()，它返回一个新的排序集合：
1 | >>> sorted([5, 2, 3, 1, 4]) |
2 | [1, 2, 3, 4, 5] |
你也可以使用list.sort()方法，它会修改集合本身，返回值为None。 通常它没有sorted()方法，但是如果你不需要原来的集合，它在性能上会稍微高效一点。
1 | >>> a = [5, 2, 3, 1, 4] |
2 | >>> a.sort() |
3 | >>> a |
4 | [1, 2, 3, 4, 5] |
另一个不同的地方是方法list.sort()只定义在集合中，相反，函数sorted()接受任何迭代器。
1 | >>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'}) |
2 | [1, 2, 3, 4, 5] |
Key
list.sort()和sorted()都有一个参数key，用来指定在每一个集合元素进行比较之前调用的函数。
例如， 这里有一个不区分大小写的字符串比较：
1 | >>> sorted("This is a test string from Andrew".split(), key=str.lower) |
2 | ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This'] |
参数key的值必须是一个函数，它有一个参数，并且返回一个用来进行排序比较的键。 这个技术性能很好，因为对每一个输入记录函数key只调用一次。
一个公共的模式是使用一些对象的索引作为键对复杂的对象进行排序，例如：
1 | >>> student_tuples = [ |
2 | ... ('john', 'A', 15), |
3 | ... ('jane', 'B', 12), |
4 | ... ('dave', 'B', 10), |
5 | ... ] |
6 | >>> sorted(student_tuples, key=lambda student: student[2]) # sort by age |
7 | [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
相同的技术也适用于有名称属性的对象。例如：
1 | >>> class Student: |
2 | ... def __init__(self, name, grade, age): |
3 | ... self.name = name |
4 | ... self.grade = grade |
5 | ... self.age = age |
6 | ... def __repr__(self): |
7 | ... return repr((self.name, self.grade, self.age)) |
8 | |
9 | >>> student_objects = [ |
10 | ... Student('john', 'A', 15), |
11 | ... Student('jane', 'B', 12), |
12 | ... Student('dave', 'B', 10), |
13 | ... ] |
14 | >>> sorted(student_objects, key=lambda student: student.age) # sort by age |
15 | [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
Operator Module Functions
上面显示的key-function模式很常见，所以Python提供了更方便的函数用来使访问功能更简单更快。operator模块有itemgetter()、attrgetter()和methodcaller()函数。
使用这些函数，上面的例子会更简单更快：
1 | >>> from operator import itemgetter, attrgetter |
2 | |
3 | >>> sorted(student_tuples, key=itemgetter(2)) |
4 | [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
5 | |
6 | >>> sorted(student_objects, key=attrgetter('age')) |
7 | [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
operator模块的函数允许多级排序。例如，用grade跟age排序：
1 | >>> sorted(student_tuples, key=itemgetter(1,2)) |
2 | [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)] |
3 | |
4 | >>> sorted(student_objects, key=attrgetter('grade', 'age')) |
5 | [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)] |
升序和降序
list.sort()和sorted()两个都接受一个布尔值的参数reverse。它用来标记降序排序。例如，按照年龄相反的顺序获取学生数据：
1 | >>> sorted(student_tuples, key=itemgetter(2), reverse=True) |
2 | [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] |
3 | |
4 | >>> sorted(student_objects, key=attrgetter('age'), reverse=True) |
5 | [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] |
排序稳定性和复杂排序
排序是保证稳定的。这意味着当有多个记录有相同的key时，将会保留他们原始的顺序。
1 | >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] |
2 | >>> sorted(data, key=itemgetter(0)) |
3 | [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)] |
注意是如何保证两个blue记录的原始顺序的，以便('blue', 1)保证优先于('blue', 2)。
这个奇妙的属性让你在一系列的排序步骤中创建复杂的排序。例如，根据grade倒序和age升序对学生数据进行排序，先执行age排序再使用grade进行排序：
1 | >>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key |
2 | >>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending |
3 | [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
在Python中使用Timsort算法进行有效的多种排序，因为它可以利用已经存在于数据集中的任何排序。
使用Decorate-Sort-Undecorate的旧方式
This idiom is called Decorate-Sort-Undecorate after its three steps:
- 首先，初始列表使用控制排序顺序的新值进行装饰。
- 第二部，对装饰的集合进行排序
- 最后，删除装饰，在新的顺序里面创建一个只包含初始化值的集合
例如，使用DSU方法根据grade对学生数据进行排序：
1 | >>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)] |
2 | >>> decorated.sort() |
3 | >>> [student for grade, i, student in decorated] # undecorate |
4 | [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] |
这个用法可行是因为元祖按照字典顺序进行比较；比较第一个元素；如果他们相同则比较第二个元素，依次类推。
在所有情况下，并不会严格要求将索引i包含在装饰列表中，但是包含它会有2个好处：
- 排序是稳定的–如果2个元素有相同的key，那么他们的顺序将被保留在排序集合中。
- 原始项目不必是可比较的，因为装饰元组的顺序最多由前两个项目决定。
因此，原始列表可能包含不能直接排序的复数。
这个用法的另外一个名字是Schwartzian transform，在Randal L. Schwartz之后，它在Perl语言中被普及。
现在Python排序提供了key-functions，这些技术不是经常需要的。
使用参数cmp的旧方式
在HOWTO假设中给出的许多结构是在Python2.4或者更高版本。在这之前，没有内置的sorted()，并且list.sort()没有keyword参数。相反，所有的Py2.x版本都支持一个cmp参数来处理用户指定的比较功能。
在Py3.0中，这个cmp参数被完全移出(作为简化和统一语言的一部分，消除了比较和魔法方法__cmp__()的冲突)。
在Py2.x中，排序允许一个可选的函数用来在进行比较的时候调用。这个函数应该把2个参数进行比较，如果小于返回一个负值，如果他们相等就返回0，如果大于就返回一个正数。例如，我们可以这样做：
1 | >>> def numeric_compare(x, y): |
2 | ... return x - y |
3 | >>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) |
4 | [1, 2, 3, 4, 5] |
你也可以颠倒比较的顺序：
1 | >>> def reverse_numeric(x, y): |
2 | ... return y - x |
3 | >>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) |
4 | [5, 4, 3, 2, 1] |
当把代码从Python 2.x 迁移到3.x，当用户指定了比较函数并且需要将它转换为key函数时会出现问题。下面这个封装可以让你跟简单的去做这些操作：
1 | def cmp_to_key(mycmp): |
2 | 'Convert a cmp= function into a key= function' |
3 | class K: |
4 | def __init__(self, obj, *args): |
5 | self.obj = obj |
6 | def __lt__(self, other): |
7 | return mycmp(self.obj, other.obj) < 0 |
8 | def __gt__(self, other): |
9 | return mycmp(self.obj, other.obj) > 0 |
10 | def __eq__(self, other): |
11 | return mycmp(self.obj, other.obj) == 0 |
12 | def __le__(self, other): |
13 | return mycmp(self.obj, other.obj) <= 0 |
14 | def __ge__(self, other): |
15 | return mycmp(self.obj, other.obj) >= 0 |
16 | def __ne__(self, other): |
17 | return mycmp(self.obj, other.obj) != 0 |
18 | return K |
转为key函数，只需要封装旧的比较函数：
1 | >>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric)) |
2 | [5, 4, 3, 2, 1] |
在Python3.2中，标准库中的functools模块添加了functools.cmp_to_key()函数。
Odd and Ends
对于区域感知排序，使用
locale.strxfrm()作为key函数或者使用locale.strcoll()作为比较函数。reverse参数一直保持排序稳定性（所以相同key的记录会保留原始的顺序），有趣的是，这个效果可以通过两次内置函数reversed()来模拟：
1 | >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] |
2 | >>> standard_way = sorted(data, key=itemgetter(0), reverse=True) |
3 | >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0)))) |
4 | >>> assert standard_way == double_reversed |
5 | >>> standard_way |
6 | [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)] |
- 当两个对象进行比较时，排序保证使用
__lt__()。所以，可以通过定义__lt__()方法，可以很方便的向类添加标准排序顺序：
1 | >>> Student.__lt__ = lambda self, other: self.age < other.age |
2 | >>> sorted(student_objects) |
3 | [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] |
- Key函数不需要直接依赖于正在排序的对象。key函数也可以访问外部资源。例如，如果学生成绩存储在字典中，可以使用它来对分离出来的学生名称集合进行排序：
1 | >>> students = ['dave', 'john', 'jane'] |
2 | >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'} |
3 | >>> sorted(students, key=newgrades.__getitem__) |
4 | ['jane', 'dave', 'john'] |
