python 内置的排序函数

排序是非常常见的操作,常见的排序算法的时间复杂度一般为 \(O(n^2)\)(冒泡、选择、插入)或 \(O(nlogn)\)(快排、归并等)。虽然这些算法对于编程人员来说是基础,但是在实际工程中往往会使用语言内置的排序函数,主要是考虑到编程效率和自己编写排序函数时涵盖情况不全的问题。因此本文主要讲述 python 中的内置函数。

python 内置的排序函数主要有两个:sortsorted,两者主要以下几点区别 (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))
# 不用key参数时也不会报错,这时排序依据默认是组合元素中的第一个元素,但是为了程序的清晰性,还是建议使用key参数
>>> 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) # sort by 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:
# @param {integer[]} nums
# @return {string}
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:
# @param {integer[]} nums
# @return {string}
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)