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)
>>> 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]
复制代码
快速排序python实现
可以看出返回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.age = age
def __repr__(self):
return repr((self.name, ade, 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（样本排序）。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。