排序是非常常见的操作,常见的排序算法的时间复杂度一般为 (冒泡、选择、插入)或 (快排、归并等)。虽然这些算法对于编程人员来说是基础,但是在实际工程中往往会使用语言内置的排序函数,主要是考虑到编程效率和自己编写排序函数时涵盖情况不全的问题。因此本文主要讲述 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' ,'A' ,'b' ,'B' ]>>> sorted (a)['A' , 'B' , 'a' , 'b' ] >>> a['a' , 'A' , 'b' , 'B' ] >>> a = ['abundunt' ,'Array' ,'bunch' ,' >>> 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 8 >>> b = ((2 ,1 ),(1 ,3 ),(4 ,2 ))>>> sorted (b) [(1 , 3 ), (2 , 1 ), (4 , 2 )] >>> sorted (b, key = lambda x:x[0 ])[(1 , 3 ), (2 , 1 ), (4 , 2 )] >>> sorted (b, key = lambda x:x[1 ])[(2 , 1 ), (4 , 2 ), (1 , 3 )]
给 key 参数传进去的是一个函数,上面使用
lambda
实现,
传入的是需要排序的组合元素,返回的是根据组合元素中哪个元素排序,从下标 0 开始计算 。
对于字典的 key 或 value 排序也是如此,但此时的下标就只有 0 和 1 了,分别代表 key 和 value。
1 2 3 4 5 6 7 8 9 >>> d = {2 :1 , 4 :3 , 1 :6 }>>> sorted (d.items(), key = lambda x:x[0 ])[(1 , 6 ), (2 , 1 ), (4 , 3 )] >>> d{1 : 6 , 2 : 1 , 4 : 3 } >>> sorted (d.items(), key = lambda x:x[1 ])[(2 , 1 ), (4 , 3 ), (1 , 6 )] >>> d{1 : 6 , 2 : 1 , 4 : 3 }
除了内部的 list、tuple 等数据类型,key 还可以针对自定义的数据类型进行排序。实例如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 >>> 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)) 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 ), ] >>> sorted (student_objects, key=lambda student: student.age) [('dave' , 'B' , 10 ), ('jane' , 'B' , 12 ), ('john' , 'A' , 15 )]
cmp 参数 利用上面两个参数已经能解决大部分的问题了,还有一些较特殊的排序需要编写特定的排序函数,这时就需要利用 cmp
参数。
如 LeetCode 上的这道题目 179. Largest Number ,就是一道排序的题目,且排序的要求是对于两个字符串 s1,s2
1 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 6 7 >>> cmp(1 ,2 )-1 >>> cmp(2 ,1 )1 >>> cmp(2 ,2 )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 2 3 4 5 6 7 class Solution : def largestNumber (self, nums ): snums = [str (num) for num in nums] snums.sort(cmp=lambda x,y: cmp(y+x,x+y)) return '' .join(snums).lstrip('0' ) or '0'
关键点在 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution : def largestNumber (self, nums ): snums = [str (num) for num in nums] self .quick_sort(0 , len (snums)-1 , snums) tmp = '' .join(snums).lstrip('0' ) return tmp if tmp else '0' def quick_sort (self, left, right, nums ): if left > right: return pivot, start, end = left, left, right while left < right: while left < right and nums[right]+nums[pivot] <= nums[pivot]+nums[right]: right -= 1 while left < right and nums[left]+nums[pivot] >= nums[pivot]+nums[left]: left += 1 if left < right: nums[left], nums[right] =nums[right], nums[left] if left == right: nums[pivot], nums[left] = nums[left], nums[pivot] self .quick_sort(start, left-1 , nums) self .quick_sort(left+1 , end, nums)