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参数即可。示例如下所示：

>>> 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的排序

>>> 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。

>>> 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还可以针对自定义的数据类型进行排序。实例如下

>>> 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)假如 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的一个内置函数。其定义如下：

>>> 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函数，我们可以写出下面较为简洁的代码

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。

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)