python 内置的排序函数

发表于 标签

排序是非常常见的操作，常见的排序算法的时间复杂度一般为 \(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','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)