02.编程学习--Python 排序

文：郑元春
一个有着美好梦想的coder！

人生苦短，我用Python。

P.S. 个人认为，查找和排序是算法的核心，同时又是在实际应用中使用率最高。今天就说说Python里面的排序吧！

ox01:string的排序函数 -- s.sort()

s.sort([cmp[, key[, reverse]]])

sort the items of s in place

喜欢原版英文文档的同学就直接看原版的英文文档吧(为了方便阅读，我把英文原版文档放在了本文最后面)，文档还是看原版的比较准确。

sort()函数和reverse()函数都是原地操作的（就是不会返回数据，直接在原有的数据上面操作，执行sort或者是reverse之后，你原始的数据将会被改变）。除了最基本的功能之外，sort()函数还有可选择的参数来完成一些高级或是定制的排序操作。排序的核心就是你定义的比较规则（cmp函数），只有比较才能分出高低来。cmp是用户自己指定比较规则，这个函数会接受两个参数（也就是list的element），通过比较你的第一个参数与第二个参数的关系（小，等于，大）规则函数会返回负数，0或正数。

• 默认情况下，直接sort()

将字符串list排序，注意的是需要注意大小写问题，大写字符要比相应的小写字符靠前，原因是大写字符的Ascii值要靠前。Ascii[A]=65, Ascii[a]=97.

#假设我们有一个字符串list（网站的所有用户的用户名），现在需要按照字母表顺序进行排序。
usernameList=['Lily','Nancy','John','Micky','Andrew','XiaoMingZhang','LiHua']
usernameList.sort()
#结果是:
['Andrew', 'John', 'LiHua', 'Lily', 'Micky', 'Nancy', 'XiaoMingZhang']

#如果是想按照倒序排的话，需要将reverse设置为True
usernameList=['Lily','Nancy','John','Micky','Andrew','XiaoMingZhang','LiHua']
usernameList.sort(reverse=True)
#结果是:
['XiaoMingZhang', 'Nancy', 'Micky', 'Lily', 'LiHua', 'John', 'Andrew']

#大小写混乱的情况
usernameList=['lily','Nancy','john','micky','andrew','XiaoMingZhang','LiHua']
usernameList.sort()
#结果是(大写的先排)：
['LiHua', 'Nancy', 'XiaoMingZhang', 'andrew', 'john', 'lily', 'micky']

• 选取部分字符排序（注意是字符，不是字符串）

这时候你会看到排序的规则是按照第一个字符字典序排列，当第一个字符一样的情况下就去排第二个字符，依次类推。有时候我们需要按照某个位置排序，或是将字符串某个位置之后的排序（因为有的情况下所有的字符串会有一个相同/不同的前缀，比如区号，自定义代码等会对排序造成干扰）。这时候就使用key来指定参加排序的关键字了。

usernameList=[
'EN_lily',
'EN_Nancy',
'EN_John',
'EN_Micky',
'EN_Andrew',
'CN_XiaoMingZhang',
'CN_LiHua']

usernameList.sort()
#结果是：
['CN_LiHua',
 'CN_XiaoMingZhang',
 'EN_Andrew',
 'EN_John',
 'EN_Micky',
 'EN_Nancy',
 'EN_lily']

usernameList.sort(key=lambda x: x[3:])
#结果是：
['EN_Andrew',
 'EN_John',
 'CN_LiHua',
 'EN_Micky',
 'EN_Nancy',
 'CN_XiaoMingZhang',
 'EN_lily']

同时，前面提到的字符大小写问题就可以解决了，这里的key的功能更像是一个map函数的功能，我先将原始的待排序的数据做下预处理，可以是挑选一部分字符排序 ，可以是将字符转换成统一大小写。也可以将字符映射成其他的，只要是你映射之后可以被cmp规则处理就行。

• 指定正序还是逆序

reverse参数指定的就是正序还是逆序，True为正序。在介绍第一个参数的时候已经介绍过了。

总结：

对于字符串的排序更多用在文本处理或者是简单的操作中，因为上面举得例子中如果在互联网应用中的话，这些操作在数据库就能够直接排序了，但是有的时候你必须使用Python的排序方法，比如你的后台开启多线程抓取数据，或是后台从不同的网站抓数据，可以直接就排序了。

0x02.sorted()

sorted(iterable[, cmp[, key[, reverse]]])

Return a new sorted list from the items in iterable.

对于sort()函数来说，一般用在list上。但Python内建的函数sorted()可用的范围就比较大了，适用于所有的iterable data。相比于sort()函数一个最大的不同就是sorted()函数不会在原始的数据上做"手脚",他会返回一个排好的list。

1. iterable：是可迭代类型;

2. cmp：用于比较的函数，比较什么由key决定;

3. key：用列表元素的某个属性或函数进行作为关键字，有默认值，迭代集合中的一项;

4. reverse：排序规则. reverse = True 降序 或者 reverse = False 升序，有默认值。

5. 返回值：是一个经过排序的可迭代类型，与iterable一样。

其实大多数的使用方式和list的sort()函数一样。

• 最简单的使用方式

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

• key 函数
  从2.4版本之后，list.sort()和sorted()函数都同时添加了key参数，指定iterable data中需要排序的数据。

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

key是个只接受单个参数的函数，它返回一个用来进行排序的key，之后的排序就是使用这个key进行排序，相当于上面提到的数据预处理了。官方文档里面说这项技术是fast的，因为对于每个输入这个key函数只执行一次。看完下面的例子你就会知道为什么我会在前面的段落中说这个key函数像是一个筛选操作。

student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]
>>> sorted(student_tuples, key=lambda student: student[2])   # 年龄排序
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

学过数据库的同学一定会联想到order by 操作了吧！是的，在数据库操作中，我们可以select多column的数据，然后通过指定一行或是多行进行排序。同时不仅能指定tuple的排序key，还能对对象list的排序key进行指定（下面的例子）

>>> 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)   
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

• 更简单的使用key函数
  不得不说。Python真是为码农考虑的太周到了，上面通过对象的attribute进行key排序的已经很人性化了，但是，Python提供了itemgetter和attrgetter两个方法来进行更人性化的操作。废话不多说，看例子。

from operator import itemgetter, attrgetter
>>>
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>>
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

如果是你需要排序的iterable data里面每个element是tuple的话，那就使用itemgetter函数进行key的筛选好了，如果iterable data里面的每个element是对象的话那就使用attrgetter函数进行key筛选好了，这样你连那个lambda函数的功夫也就省了（对于我这种小coder来说，两者好像没什么区别嘛）

• key的多级排序
  上面提到过的数据库会运行coder指定多个column对select结果进行多级排序，同样Python的itemgetter和attrgetter也是支持多级排序的。

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

• key的另一种“筛选”数据的方式
  其实，key的作用除了简单的“筛选”功能之外，还有很多的其他有意思的功能。将要排序的原始数据映射到另一个数据空间中，更像一个map函数的操作。
  通过结合operator.methodcaller()函数，下面的例子比较有趣：

 messages = ['critical!!!', 'hurry!', 'standby', 'immediate!!']
>>> sorted(messages, key=methodcaller('count', '!'))
['standby', 'hurry!', 'immediate!!', 'critical!!!']

从这个例子来看的话，对iterable data中的每个元素（这里是字符串）进行count("!")操作，将返回的“！”个数作为排序的依据。

• 正序+逆序
  使用reverse参数就能控制逆序还是顺序了，和上一段用法一样。

总结：

Python的排序真的是让人喜欢的很啊，从最初始的基本功能，到各种高级功能，同时还支持key函数和自己定义的cmp函数，这些用户自行编写的功能函数很好的扩展了sort的功能，说其“三头六臂”也不为过啊！

• key函数目的是找出排序依据，通过对原始数据预处理（选数据的一部分，计算元素个数等）来找出排血的基础，这才是key的真正意义吧，有的时候你的排序操作有可能就不是对原始数据做排序处理了。

• cmp函数的目的是制定排序规则，通过用户自定义的排序函数，可以实现定制功能，只要你的返回符合他的规则就行了。

• reverse参数简单的使用True或者是False就能翻转排序结果，用户体验很好。

文章的最后放上官方的文档作为原始的参考。

The sort() and reverse() methods modify the list in place for economy of space when sorting or reversing a large list. To remind you that they operate by side effect, they don’t return the sorted or reversed list.

The sort() method takes optional arguments for controlling the comparisons.

cmp specifies a custom comparison function of two arguments (list items) which should return a negative, zero or positive number depending on whether the first argument is considered smaller than, equal to, or larger than the second argument: cmp=lambda x,y: cmp(x.lower(), y.lower()). The default value is None.

key specifies a function of one argument that is used to extract a comparison key from each list element: key=str.lower. The default value is None.

reverse is a boolean value. If set to True, then the list elements are sorted as if each comparison were reversed.

In general, the key and reverse conversion processes are much faster than specifying an equivalent cmp function. This is because cmp is called multiple times for each list element while key and reverse touch each element only once. Use functools.cmp_to_key() to convert an old-style cmp function to a key function.

Changed in version 2.3: Support for None as an equivalent to omitting cmp was added.

Changed in version 2.4: Support for key and reverse was added.

Starting with Python 2.3, the sort() method is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).

The optional arguments cmp, key, and reverse have the same meaning as those for the list.sort() method (described in section Mutable Sequence Types).

cmp specifies a custom comparison function of two arguments (iterable elements) which should return a negative, zero or positive number depending on whether the first argument is considered smaller than, equal to, or larger than the second argument: cmp=lambda x,y: cmp(x.lower(), y.lower()). The default value is None.

key specifies a function of one argument that is used to extract a comparison key from each list element: key=str.lower. The default value is None (compare the elements directly).

reverse is a boolean value. If set to True, then the list elements are sorted as if each comparison were reversed.

In general, the key and reverse conversion processes are much faster than specifying an equivalent cmp function. This is because cmp is called multiple times for each list element while key and reverse touch each element only once. Use functools.cmp_to_key() to convert an old-style cmp function to a key function.

The built-in sorted() function is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).

参考：

• 字符串sort()官方文档
• sorted()函数文档
• sorted() 官方例子