Question

各种排序算法以及它们的时间复杂度分析是很多企业面试人员在面试时候经常会问到的问题，这也不难理解，在实际的应用过程中确实会遇到各种需要排序的情况，如按照字母表输出一个序列、对记录的多个字段排序等。还好，Python中的排序相对简单，常用的函数有sort()和sorted()两种。这两种函数并不完全相同，各有各的用武之地。我们来具体分析一下。

1）相比于sort()，sorted()使用的范围更为广泛，两者的函数形式分别如下：

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

这两个方法有以下3个共同的参数：

cmp为用户定义的任何比较函数，函数的参数为两个可比较的元素（来自iterable或者list），函数根据第一个参数与第二个参数的关系依次返回-1、0或者+1（第一个参数小于第二个参数则返回负数）。该参数默认值为None。

key是带一个参数的函数，用来为每个元素提取比较值，默认为None（即直接比较每个元素）。

reverse表示排序结果是否反转。

>>> persons = [{'name': 'Jon', 'age': 32}, {'name': 'Alan', 'age': 50}, {'name':
 'Bob', 'age': 23}]
>>> sorted(persons, key=lambda x: (x['name'], -x['age']))
[{'age': 50, 'name': 'Alan'}, {'age': 23, 'name': 'Bob'}, {'age': 32, 'name': 'J
on'}]

从函数的定义形式可以看出，sorted()作用于任意可迭代的对象，而sort()一般作用于列表。因此下面的例子中针对元组使用sort()方法会抛出AttributeError，而使用sorted()函数则没有这个问题。

>>> a = (1,2,4,2,3)
>>> a.sort()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'tuple' object has no attribute 'sort'
>>> sorted(a)
[1, 2, 2, 3, 4]

2）当排序对象为列表的时候两者适合的场景不同。sorted()函数是在Python2.4版本中引入的，在这之前只有sort()函数。sorted()函数会返回一个排序后的列表，原有列表保持不变；而sort()函数会直接修改原有列表，函数返回为None。来看下面的例子：

>>> a=['1',1,'a',3,7,'n']
>>> sorted(a)
[1, 3, 7, '1', 'a', 'n']
>>> a
['1', 1, 'a', 3, 7, 'n']
>>> print a.sort()
None
>>> a
[1, 3, 7, '1', 'a', 'n']
>>>

因此如果实际应用过程中需要保留原有列表，使用sorted()函数较为适合，否则可以选择sort()函数，因为sort()函数不需要复制原有列表，消耗的内存较少，效率也较高。

3）无论是sort()还是sorted()函数，传入参数key比传入参数cmp效率要高。cmp传入的函数在整个排序过程中会调用多次，函数开销较大；而key针对每个元素仅作一次处理，因此使用key比使用cmp效率要高。下面的测试例子显示使用key比cmp约快50%。

>>> from timeit import Timer
>>> Timer(stmt="sorted(xs,key=lambda x:x[1])",setup="xs=range(100);xs=zip(xs,xs)
;").timeit(10000)
0.2900448249509081
>>>
>>> Timer(stmt="sorted(xs,cmp=lambda a,b: cmp(a[1],b[1]))",setup="xs=range(100);
xs=zip(xs,xs);").timeit(10000)
0.47374972749250155
>>>

4）sorted()函数功能非常强大，使用它可以方便地针对不同的数据结构进行排序，从而满足不同需求。来看下列例子。

对字典进行排序：下面的例子中根据字典的值进行排序，即将phonebook对应的电话号码按照数字大小进行排序。

>>> phonebook = {'Linda': '7750', 'Bob': '9345', 'Carol': '5834'}
>>> from operator import itemgetter
>>> sorted_pb = sorted(phonebook.iteritems(),key=itemgetter(1))
>>> print sorted_pb
[('Carol', '5834'), ('Linda', '7750'), ('Bob', '9345')]
>>>

多维list排序：实际情况下也会碰到需要对多个字段进行排序的情况，如根据学生的成绩、对应的等级依次排序。当然这在DB里面用SQL语句很容易做到，但使用多维列表联合sorted()函数也可以轻易达到类似的效果。

>>> from operator import itemgetter
>>> gameresult = [['Bob',95.00,'A'],['Alan',86.0,'C'],['Mandy',82.5,'A'],['Rob',
86,'E']] #
分别表示学生的姓名，成绩，等级
>>> sorted(gameresult , key=operator.itemgetter(2, 1))
[['Mandy', 82.5, 'A'], ['Bob', 95.0, 'A'], ['Alan', 86.0, 'C'], ['Rob', 86, 
    'E'] #
当第二个字段成绩相同的时候按照等级从低到高排序
]

字典中混合list排序：如果字典中的key或者值为列表，需要对列表中的某一个位置的元素排序也是可以做到的。下面的例子中针对字典mydict的value结构[n,m]中的n按照从小到大的顺序排列。

>>> mydict = { 'Li': ['M',7],
...      'Zhang': ['E',2],
...      'Wang': ['P',3],
...      'Du': ['C',2],
...      'Ma': ['C',9],
...      'Zhe': ['H',7] }
>>>
>>> from operator import itemgetter
>>> sorted(mydict.iteritems(), key=lambda (k,v): operator.itemgetter(1)(v))
[('Zhang', ['E', 2]), ('Du', ['C', 2]), ('Wang', ['P', 3]), ('Li', ['M', 7]), ('
Zhe', ['H', 7]), ('Ma', ['C', 9])]

List中混合字典排序：如果列表中的每一个元素为字典形式，需要针对字典的多个key值进行排序也不难实现。下面的例子是针对list中的字典元素按照rating和name进行排序的实现方法。

>>> gameresult = [{ "name":"Bob", "wins":10, "losses":3, "rating":75.00 },
...       { "name":"David", "wins":3, "losses":5, "rating":57.00 },
...       { "name":"Carol", "wins":4, "losses":5, "rating":57.00 },
...       { "name":"Patty", "wins":9, "losses":3, "rating": 71.48 }]
>>> from operator import itemgetter
>>> sorted(gameresult , key=operator.itemgetter("rating","name"))
[{'wins': 4, 'losses': 5, 'name': 'Carol', 'rating': 57.0}, {'wins': 3, 'losses'
: 5, 'name': 'David', 'rating': 57.0}, {'wins': 9, 'losses': 3, 'name': 'Patty',
 'rating': 71.48}, {'wins': 10, 'losses': 3, 'name': 'Bob', 'rating': 75.0}]
>>>