这部分内容可参考： https://blog.51cto.com/u_16213676/7008806
各种排序算法以及它们的时间复杂度分析是很多企业面试人员在面试时候经常会问到的问题。
这也不难理解，在实际的应用过程中确实会遇到各种需要排序的情况，如按照字母表 输出一个序列、对记录的多个字段排序等。
还好，Python中的排序相对简单，常用的函数有 sort() 和 sorted() 两种。
这两种函数并不完全相同，各有各的用武之地。我们来具体分析一下。
两个函数的差别
相比于 sort() , sorted()使用的范围更为广泛，两者的函数形式分别如下：
sorted(iterable[, cmp[f key[, reverse])s.sort([cmp[, key[, reverse]])这两个方法有以下3个共同的参数：
注意：在Python 3 中废弃了 sorted() 函数中的 cmp 参数。
cmp为用户定义的任何比较函数，函数的参数为两个可比较的元素（来自itewble或者list), 函数根据第一个参数与第二个参数的关系依次返回-1、0或者+1(第一个参 数小于第二个参数则返回负数)。 该参数默认值为None。key是带一个参数的函数，用来为每个元素提取比较值，默认为None(即直接比较每个元素）。reverse表示排序结果是否反转。
persons =[{'name':"Jon•t" ,'age': 32},
{'name': 'Alan1r ','age': 50},
{'name': 'Bob ','age' : 23}]
sorted(persons ,key=lambda x:(x["name"],-x["age"]))
[{'name': 'Alan1r ', 'age': 50},
{'name': 'Bob ', 'age': 23},
{'name': 'Jon•t', 'age': 32}]
从函数的定义形式可以看出， sorted() 作用于任意可迭代的对象，
sort() —般作用于列 表。
因此下面的例子中针对元组使用 sort() 方法会抛出 AttributeError ，
而使用 sorted() 函数则没有这个问题。
a=(1,2,9,4,5)
# a.sort()
sorted(a)
[1, 2, 4, 5, 9]
当排序对象为列表的时候两者适合的场景不同。
sorted() 函数是在Python2.4版本中引人的，在这之前只有 sort()函数。
sorted() 函数会返回一个排序后的列表，原有列表保持不 变；
而 sort() 函数会直接修改原有列表，函数返间为 None 。
来看下面的例子：
a=["1","2","3","b","4","a","3"]
sorted(a)
['1', '2', '3', '3', '4', 'a', 'b']
a
['1', '2', '3', 'b', '4', 'a', '3']
a.sort()
a
['1', '2', '3', '3', '4', 'a', 'b']
因此如果实际应用过程中需要保留原有列表，使用 sorted() 函数较为适合，否则可以选 择 sort() 函数，
因为 sort() 函数不需要复制原有列表，消耗的内存较少，效率也较高。
无论是 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)
# Timer(stmt="sorted(xs,cmp=lambda ,b:cmp(a[1],b[1]))",setup="xs=range(100);xs=zip(xs,xs);").timeit(10000)
0.0024263579998660134
Python3 没有 cmp 函数了 。
from timeit import Timer
Timer(stmt="sorted(xs,key=lambda x:x[1])",setup="xs=range(100);xs=zip(xs,xs);").timeit(10000)
0.0024128519999067066
Python3中没有cmp函数所以会报错：
# Timer(stmt="sorted(xs,cmp=lambda a,b:cmp(a[1],b[1]))",setup="xs=range(100);xs=zip(xs,xs);").timeit(10000)
sorted() 函数功能非常强大，使用它可以方便地针对不同的数据结构进行排序，从而 满足不同需求。来看下列例子。
- 对字典进行排序：下面的例子中根据字典的值进行棑序，即将
Phonebook对应的电话 号码按照数字大小进行排序。
Phonebook = {'Linda': '7750', 'Bob': '9345' ,'Carol': '5834'}
from operator import itemgetter
sorted_pb = sorted(Phonebook.items(),key=itemgetter(1))
print (sorted_pb)
[('Carol', '5834'), ('Linda', '7750'), ('Bob', '9345')]
from operator import itemgetter
gameresult =[[ "Bob",95.00, 'A'],[" Alan" , 86.00, " C" ] ,
['Mandy',82.5,'A'], [" Rob" ,86,"E"]]
sorted(gameresult,key=itemgetter(2,1))
[[' Alan', 86.0, ' C'], ['Mandy', 82.5, 'A'], ['Bob', 95.0, 'A'], [' Rob', 86, 'E']]
当第二个字段成缋相同的时候按照等级从低到离排序：
sorted (gameresult , key=itemgetter (2, 1))
[[' Alan', 86.0, ' C'], ['Mandy', 82.5, 'A'], ['Bob', 95.0, 'A'], [' Rob', 86, 'E']]
python2 内可执行
python3 内可执行
#python3 内可执行
mydict = {
'Li': ['M',7],
'Zhang': ['E',2],
'Wang': ["P",3],
'Du1': ["C",2],
'Ma': ["C",9],
'Zhe': ["H",7]
}
from operator import itemgetter
sorted_items = sorted(
mydict.items(), # 改用 items() 代替 iteritems()
key=lambda x: x[1][1] # 使用单个参数并双重索引访问
)
print(sorted_items)
[('Zhang', ['E', 2]), ('Du1', ['C', 2]), ('Wang', ['P', 3]), ('Li', ['M', 7]), ('Zhe', ['H', 7]), ('Ma', ['C', 9])]
gameresult= [{ "name" : " Bob","wins" : 10, "losses":3, "rating" : 75.00 },
{"name":"David", "wins":3,"losses":5, "rating":57.00},
{ "name":"Carol", "wins":4," Mlosses":5, "rating":57.00},
{"name": "Patty", "wins":9,"losses" :3, "rating": 71.48}]
from operator import itemgetter
sorted (gameresult , key=itemgetter ("rating","name"))#python2 执行
[{'name': 'Carol', 'wins': 4, ' Mlosses': 5, 'rating': 57.0},
{'name': 'David', 'wins': 3, 'losses': 5, 'rating': 57.0},
{'name': 'Patty', 'wins': 9, 'losses': 3, 'rating': 71.48},
{'name': ' Bob', 'wins': 10, 'losses': 3, 'rating': 75.0}]