# [python]排序（Sorting Mini-HOW TO）

Python 内置的 `sort()` 方法可以实现对列表的原地排序功能。内置的 `sorted()` 函数则不会修改原列表，而是生成一个经过排序的新列表。

## 基本排序

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

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

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

## 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 进行排序）。

```>>> 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:
self.name = name
self.age = age
def __repr__(self):

>>> 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 模块函数

```>>> 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:
self.name = name
self.age = age
def __repr__(self):

>>> 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)]
```

```>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

[('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）排序和复杂排序

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

```>>> class Student:
self.name = name
self.age = age
def __repr__(self):

>>> 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)]
```

## 以前的实现方式(使用 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]
```

## 其他

• 对于本地化排序，可以使用 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'}