python排序

发表于 | 更新于 | 分类于

基本排序

sorted()返回新的list

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

list.sort()修改原有的list

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

list.sort()方法只能作用于列表，而 sorted()函数则接受任何可迭代对象

升降序

list.sort() 和 sorted() 都接受一个布尔类型的 reverse 参数。这个参数用来标记是否使用降序排序

key函数

从 Python 2.4 开始， list.sort() 和 sorted() 增加了一个 key 参数，该参数接受一个函数作为它的值，可以通过那个函数定义排序应该遵循的规则。
key 参数的值必须是个函数，该函数有一个参数（列表元素）并且返回一个用来排序的 key（按这个 key 进行排序）。

1
2
3
4
5
6
7
8
>>> student_tuples = [
        ('Chi', 'A', 15),
        ('Qin', 'B', 12),
        ('Xu', 'B', 10),
]
# 按列表元素（元组）的第3个值排序
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('Xu', 'B', 10), ('Qin', 'B', 12), ('Chi', 'A', 15)]

可以利用这个参数巧妙的构造tuple来得到排序后的原索引

1
2
3
>>> my_list = [1,0,3,2,5]
>>> [i[0] for i in sorted(enumerate(my_list), key=lambda x:x[1])]
[1, 0, 3, 2, 4]

Operator 模块函数

由于 key 参数比较常用，所以 Python 内置了一些用来简单、快速生成相关函数的方法。 operator 模块提供了 itemgetter，attrgetter， 以及从 Python 2.6 开始提供的 methodcaller 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
>>> 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 排序：

1
2
3
4
5
>>> 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 函数可以让元素调用一个方法，然后按方法的返回值进行排序：

1
2
3
4
5
6
7
>>> 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']

平衡（Stability）排序和复杂排序

从 Python 2.2 开始，排序将保证能够 stable。 这意味着当多个记录拥有相同的 key 时，它们的原始顺序将被保留。

1
2
3
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

这个非常有用的特性可以用来实现包含多重排序（一会升序，一会降序）的复杂排序。比如，目标是实现 student 数据先以 grade 降序排序再以 age 升序排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
>>> 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 排序算法能够高效的实现多重排序。

类排序

如果想给类排序的话，只需添加相关的比较方法。

1
2
3
4
5
6
7
8
>>> 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 函数也可以不访问要排序对象的相关数据，访问外部资源也是可以的。比如，学生成绩存储在一个字典中，这个字典可以用来对学生名字进行排序：

1
2
3
4
>>> students = ['dave', 'john', 'jane']
>>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
>>> sorted(students, key=newgrades.__getitem__)
['jane', 'dave', 'john']

Reference Posts:

Huang Huang 的博客：python排序（Sorting Mini-HOW TO）