你见过驴在麦尖上跑吗？——大咕咕鸡
python的sort函数与cmp参数
1.基本用法
###描述 sorted() 函数对所有可迭代的对象进行排序操作。
###语法 sorted 语法：
sorted(iterable[, cmp[, key[, reverse]]])
参数说明：
iterable -- 可迭代对象。
cmp -- 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
reverse -- 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。
返回值
返回重新排序的列表。
2.sort函数中的cmp参数
sort中的key参数使用lambda只能对取出的一个元素操作，两个值时就会报错。
而且在python2.4前，sorted()和list.sort()函数没有提供key参数，但是提供了其他语言都常用的cmp参数来让用户指定比较函数 ，默认值为None，可以传入一个具有两个参数的匿名函数。
不过在python3中为了节省内存已经取消。
本身cmp是一个独立函数：cmp(x ,y) ，当x<y会返回负数、当x>y会返回正数、当x=y则返回0。
>>> cmp(11,56)
-1
>>> cmp(56,11)
1
>>> cmp(11,11)
0
>>> cmp('abc','b')
-1
简单用法有
>>> def numeric_compare(x, y):
return x - y
>>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)
[1, 2, 3, 4, 5]
这样看起来好像没什么用，查了许多资料说的也语焉不详，来试一下：
>>> a = [-5, -2, 3, 6]
>>> sorted(a, cmp=lambda x, y: x-y)
>>> a
[-5, -2, 3, 6] # 是正常正序排序
>>> a.sort(cmp=lambda x, y: y -x)
>>> a
[6, 3, -2, -5] # 这是逆序排序
# 好玩的来了~~
>>> a = [-2, -5, 6, 3]
>>> sorted(a, cmp=lambda x, y: -x)
[3, 6, -2, -5]
>>> sorted(a, cmp=lambda x, y: -y)
[-2, -5, 3, 6]
>>> sorted(a,cmp=lambda x, y: x+y)
[-5, -2, 6, 3]
>>> sorted(a,cmp=lambda x, y: x )
[-5, -2, 6, 3]
>>> sorted(a,cmp=lambda x, y: y )
[6, 3, -5, -2]
>>> sorted(a,cmp=lambda x, y: 1 )
[-2, -5, 6, 3]
>>> sorted(a,cmp=lambda x, y: 0)
[-2, -5, 6, 3]
>>> sorted(a,cmp=lambda x, y: -1)
[3, 6, -5, -2]
>>> sorted(a,cmp=lambda x, y: True)
[-2, -5, 6, 3]
>>> sorted(a,cmp=lambda x, y: False)
[-2, -5, 6, 3]
>>> sorted(a,cmp=lambda x, y: None)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: comparison function must return int, not NoneType
# 啊哦，不能返回空值，但是说可以返回任意int类型
>>> sorted(a,cmp=lambda x, y: 5)
[-2, -5, 6, 3]
>>> sorted(a,cmp=lambda x, y: -2)
[3, 6, -5, -2]
可以看出返回True和False得到的结果相同，且与返回1,和0的结果相同，结果不同的是返回非负数和负数： 正数时，按照列表本身的顺序排列； 负数时，按照列表本身顺序的逆序排序，类似于切片步长为-1时。
要研究返回值为“-x”,“-y”，“x+y”等时，为什么会得到那种奇怪的效果，我用了pycharm 的debug来分析。
sorted(a, cmp=lambda x, y: -x)，这会创建一个副本，不会改变列表本身，之前用sorted是为了更直观观察各种不同值对列表的影响。
为了观察x,y在每一步的值，所以现在以a.sort(cmp=lambda x, y: -x)为例，整理如下：
可以看出，系统逻辑为，3要排在6之前，6要排在-2之前，而-2要在-5之前，于是得到结果。 过程中，列表a一直为空，最后一步编译器才将排列好的值填进。
至于编译器取出列表中元素依据的是什么顺序就是更底层的原理了，在此不再深究。
最后：
在pytho3中如果想要在sort函数中使用cmp参数，需要从模块导入函数from functools import cmp_to_key，然后在sort将其赋值给key，来看例子：
from functools import cmp_to_key
nums = [1, 3, 2, 4]
nums.sort(key=cmp_to_key(lambda a, b: a - b))
print(nums) # [1, 2, 3, 4]
3.sort函数调用Operator模块函数
operator模块有itemgetter，attrgetter，从2.6开始还增加了methodcaller方法。
>>> 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),
]
>>> 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')) #按列表中对象的“age”属性排序
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
允许多级的排序，例如，先以grade，然后再以age来排序：
>>> 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)]
4.python中sort函数的实现原理
C++内部的sort是由快排，直接插入和堆排序混合的，具体详情见STL源码剖析。
当数据量比较大的时候先用的快排，当数据量小的时候用直接插入，因为当数据量变小时，快排中的每个部分基本有序，接近直接插入的最好情况的时间复杂度O(n)，就比快排要好一点了。
java内部用的都是归并排序。 因为C++模板有很强的inline优化机制，比较操作相对于赋值（移动）操作要快的多（尤其是元素较大时），而java中的情况正好相反，移动（赋值）一般比比较快；另一方面，一般情况下，归并排序的比较次数小于快速排序的比较次数，而移动次数一般多于快速排序的移动次数，二者大约都是2~3倍的差距。因为这样，java标准库中的一般排序使用的归并排序的一种变种。
python内部的sort采用的是混合（hybrid）排序，规模小的时候采用binary insertion（折半插入排序），规模大的时候采用samplesort（样本排序）。
