排序是非常常见的操作,常见的排序算法的时间复杂度一般为$O(n^2)$(冒泡、选择、插入)或$O(nlogn)$(快排、归并等)。虽然这些算法对于编程人员来说是基础,但是在实际工程中往往会使用语言内置的排序函数,主要是考虑到编程效率和自己编写排序函数时涵盖情况不全的问题。因此本文主要讲述python中的内置函数。
python内置的排序函数主要有两个:sort
和sorted
,两者主要以下几点区别
(1)针对的数据类型不同,sort只能对list类型排序,sorted可对list、tuple、dictionary以及自定义的类等数据类型排序
(2)sort会修改原来的list,sorted不会修改原来的数据结构,而是将排好序的结果以list形式返回,因此sorted才能对不可变的数据类型tuple进行排序
(3)语法不同,sort的使用方法是list.sort(),sorted的使用方法是sorted(list|tuple|dict)
除此之外,两者的参数完全一致,都含有reverse,key,cmp
这几个参数,这几个参数的用法在两个函数中一致,下面以sorted
为例分别讲述这几个参数的作用。
reverse 参数
reverse参数的作用是决定从小到大还是从大到小排列结果,默认情况下reverse=False
,从小到大排列结果。如果要从大到小排列结果,添加reverse=True
参数即可。示例如下所示:1
2
3
4
5
6
7
8'a','A','b','B'] a = [
sorted(a)
['A', 'B', 'a', 'b']
a
['a', 'A', 'b', 'B']
'abundunt','Array','bunch',' a = [
>>> sorted(a, reverse = True)
['bunch', 'abundunt', 'But', 'Array']
数字大小的判断很容易理解,这里比较的是字符串的大小,比较时会根据字符串首字符的ASCII码的大小进行排序。
key 参数
上面的例子是根据单个元素来排序的,假如需要对多个元素组合而成的元素来排序(如b = [(2,1),(1,3),(4,2)]
),就需要用key来指定以哪个元素作为排序的依据。
下面是对tuple组成的tuple的排序1
2
3
4
5
6
7
82,1),(1,3),(4,2)) b = ((
# 不用key参数时也不会报错,这时排序依据默认是组合元素中的第一个元素,但是为了程序的清晰性,还是建议使用key参数
sorted(b)
[(1, 3), (2, 1), (4, 2)]
lambda x:x[0]) sorted(b, key =
[(1, 3), (2, 1), (4, 2)]
lambda x:x[1]) sorted(b, key =
[(2, 1), (4, 2), (1, 3)]
给key参数传进去的是一个函数,上面使用lambda
实现,传入的是需要排序的组合元素,返回的是根据组合元素中哪个元素排序,从下标0开始计算。
对于字典的key或value排序也是如此,但此时的下标就只有0和1了,分别代表key和value。
1 | 2:1, 4:3, 1:6} d = { |
除了内部的list、tuple等数据类型,key还可以针对自定义的数据类型进行排序。实例如下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class 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))
def weighted_grade(self):
return 'CBA'.index(self.grade) / float(self.age)
student_objects = [
Student('john', 'A', 15),
Student('jane', 'B', 12),
Student('dave', 'B', 10),
]
lambda student: student.age) # sort by age sorted(student_objects, key=
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
cmp 参数
利用上面两个参数已经能解决大部分的问题了,还有一些较特殊的排序需要编写特定的排序函数,这时就需要利用cmp
参数。
如LeetCode上的这道题目179. Largest Number,就是一道排序的题目,且排序的要求是对于两个字符串s1,s21
2
3
4排序规则如下:
(1)假如 s1+s2 > s2+s1,则 s1 > s2
(2)假如 s1+s2 < s2+s1,则 s1 < s2
(3)以上两种情况均不符合,则s1 = s2
这种情况下上面所提到的两种方法都无法实现,因为上面的两个参数都是针对单个元素的特性的,而这种方法则是针对两个元素之间的关系。因此需要定义自己的排序函数。
不指定cmp参数的时候,cmp = lambda x,y: cmp(x, y)
,这里需要注意第一个cmp是sort函数的参数,第二个cmp则是python的一个内置函数。其定义如下:1
2
3
4
5
61,2) cmp(
-1
2,1) cmp(
1
2,2) cmp(
0
对于cmp(x, y)
,当 x 大于、等于、小于 y 时,分别会返回 1,0,-1。这个默认的cmp函数也可以写成cmp = lambda x,y: x-y
,这种情况下是从小到大排序的,那么从大到小的排序可以写成cmp = lambda x,y: y-x
。这等价于reverse = True
。
回到题目179. Largest Number上,利用内置的sorted函数,我们可以写出下面较为简洁的代码
1 | class Solution: |
关键点在snums.sort(cmp=lambda x,y: cmp(y+x,x+y))
这句话,首先是cmp(y+x,x+y)
,当 y+x > x+y
时, y>x
, 此时cmp(y+x,x+y)
返回1,而由上面的知识可知这是从大到小的排序。
上面可以说是比较抽象的代码,下面是通过自己实现的快排解决上面的题目,跟上面的答案一样能够AC。
1 | class Solution: |