Python自定义排序及实际遇到的一些实例

写在前面，本文主要介绍Python基础排序和自定义排序的一些规则，如果都比较熟悉，可以直接翻到第三节，看下实际的笔试面试题中关于自定义排序的应用。

一、基础排序

排序是比较基础的算法，与很多语言一样，Python也提供了对列表的排序方法和内建排序函数。

1、两种排序方式

方式一：

li = [1, 3, 4, 9, 0]
li.sort()  # 提供方法

方式二：

li = [1, 3, 4, 9, 0]
li = sorted(li)  # 提供方法

两种方式都可以实现对列表元素的排序，从接受参数更能看出两者区别和相同点。

• sort(key=None, reverse=False)
• sorted(iterable, key, reverse)

2、不同点

（1）：sort()属于列表对象特有的排序方法，因此调用方法直接在列表本身进行修改，返回值为None或者说无需返回值。
（2）： sorted()属于python提供内建函数，无需导入可直接用，而从接受对象来看，sorted()方法可以直接接受iterable可迭代对象，因此作用对象更广泛，包括字符串，元组甚至字典都可以，返回一个列表，如下所示

test_string = "dvsegh"
print(sorted(test_string)) # 输出['d', 'e', 'g', 'h', 's', 'v']
test_tuple = (5, 4, 3, 2, 1)
print(sorted(test_tuple)) # 输出[1, 2, 3, 4, 5]
test_list = [5, 4, 3, 2, 1]
print(sorted(test_list)) # 输出[1, 2, 3, 4, 5]
test_dic = {1:"a", 2:"b", 0:"z"}
print(sorted(test_dic)) # 输出[0, 1, 2]，字典的key作为排序结果返回

（3）：对于Python3.x中的sort()无法函数自定义排序规则后面会说到。

3、相同点

（1）：都支持reverse反转操作，参数reverse接收布尔类型，比如reverse=True，则表示排序结果逆序。

li = [1, 3, 4, 9, 0]
li.sort(reverse=True)
print(li)  # [9, 4, 3, 1, 0]

（2）： 都支持关键函数排序，也就是key参数指定排序规则，参数的接收值为一个函数，该函数可以接收一个参数并返回一个值用来比较，如下，len接收字符串，返回长度作为比较值。

test_string = "Hello World Welcome to My City"
print(sorted(test_string.split(" "), key=len))  # 根据字符串长度排序
# 输出：['to', 'My', 'City', 'Hello', 'World', 'Welcome']
print(sorted(test_string.split(" "), key=str.lower))  # 根据小写之后的字典序排序  
# 输出：['City', 'Hello', 'My', 'to', 'Welcome', 'World']

test_list = [-5, 4, 0, 2, 1]
print(sorted(test_list, key=abs))  # 根据绝对值排序 
# 输出：[0, 1, 2, 4, -5]

（3）：更广泛的可以使用lambda表达式来完成更复杂排序。如下对二维列表多级排序

li = [
    [3 ,5],
    [5 ,0],
    [5 ,6],
    [3 ,-1],
    [2, 9]
]
# 多级排序
# 根据第一个元素从小打到排列，当第一个元素相等，按照第二个元素从大到小排列
li.sort(key=lambda x: (x[0], -x[1])) 
print(li)
#  输出 [[2, 9], [3, 5], [3, -1], [5, 6], [5, 0]]

也或者可以根据复杂对象的某些属性排序。对对象根据属性进行排序

# 学生对象，包括年龄，身高体重等
class Student:
    def __init__(self, age, height, weight):
        self.age = age
        self.height = height
        self.weight = weight

s1 = Student(18, 180, 75)
s2 = Student(19, 175, 80)
s3 = Student(17, 176, 70)
s4 = Student(18, 177, 65)
s5 = Student(19, 180, 65)

# 班级里有很多学生
classes = [s1, s2, s3, s4, s5]
# 根据学生的年龄排序
classes.sort(key=lambda s: s.age)
for stu in classes:
    print("stu age: %d, height: %d, weight: %d" % (stu.age, stu.height, stu.weight))
    
输出：
stu age: 17, height: 176, weight: 70
stu age: 18, height: 180, weight: 75
stu age: 18, height: 177, weight: 65
stu age: 19, height: 175, weight: 80
stu age: 19, height: 180, weight: 65

从以上排序结果中相同年龄的学生还保持排序前的相对顺序，说明sort()排序也是稳定排序，sort()底层是基于合并排序和插入排序集合的一种更高效排序算法。以上是使用lambda表达式指定排序规则，也可以使用operator中提供的其他更加简洁的方式。

# 同样适用上述的Student例子
from operator import itemgetter, attrgetter

# 实现根据学生年龄排序
print(sorted(classes, key=attrgetter('age')))
print(sorted(classes, key=itemgetter(1)))
# 实现多级排序 新根据身高，再根据年龄排序
sorted(classes, key=attrgetter('height', 'age'))

二、排序进阶

其他语言中普遍提供的有cmp函数，也就是自定义更高级函数作为排序规则。而在python3.x中sort()不在支持cmp自定义函数比较，想要使用cmp，则需要是使用sorted()，并额外的做一些包装。

1、举例

比如，同样使用如上的Student例子，想要完成自定义排序规则，比如首先按照年龄大小排序，当年龄相同的时候按照体重逆序排序，如果体重也相同则按照身高逆序排序。

from functools import cmp_to_key

def func(stu1, stu2):
    # 年龄相同
    if stu1.age == stu2.age:
        # 体重相同 安装身高逆序
        if stu1.weight == stu2.weight:
            return stu2.height - stu1.height
        else: # 体重不同，逆序排序
            return stu2.weight - stu1.weight
    else: # 年龄不同，则按照年龄排序
        return stu1.age - stu2.age

class Student:
    def __init__(self, age, height, weight):
        self.age = age
        self.height = height
        self.weight = weight

s1 = Student(18, 180, 55)
s2 = Student(19, 175, 80)
s3 = Student(17, 162, 70)
s4 = Student(18, 177, 65)
s5 = Student(19, 180, 65)
s6 = Student(16, 160, 55)
s7 = Student(17, 164, 70)

# 班级有7个学生
classes = [s1, s2, s3, s4, s5, s6, s7]
# 排序
classes = sorted(classes, key=cmp_to_key(func))
for stu in classes:
    print("stu age: %d, height: %d, weight: %d" % (stu.age, stu.height, stu.weight))
    
输出结果
stu age: 16, height: 160, weight: 55
stu age: 17, height: 164, weight: 70
stu age: 17, height: 162, weight: 70
stu age: 18, height: 177, weight: 65
stu age: 18, height: 180, weight: 55
stu age: 19, height: 175, weight: 80
stu age: 19, height: 180, weight: 65

对于sorted(iterable, key=lambda x:x)，这种比较倾向于待排序的每个元素都有一个绝对的大小值作为排序标准，而有时候会绝对大小是根据两个元素才能得出的衡量，因此可以使用如上functools.cmp_to_key构建多个元素的比较函数。cmp_to_key包装后的自定义比较函数可以接受两个元素，将两个元素的对比结果作为返回值，另外注意，自定义的比较函数返回值需要是整型。

2、源码

cmp_to_key的源码如下

def cmp_to_key(mycmp):
    """Convert a cmp= function into a key= function"""
    class K(object):
        __slots__ = ['obj']
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        __hash__ = None
    return K

cmp_to_key接收myfunc，并在内部定义一个K类并返回这个K类，这个类内部完成了各种比较运算符的重载（也就是mycmp的定义的排序规则），这个类是可调用的，在参与比较的时候其实是K的对象，而在使用lambda匿名表达式的时候使用是列表中的元素进行大小比较。如下：

li = [1, 0, 0, 8, 4]
sorted(li, key=lambda x: x)  # x代指li中的每个元素

三、真题

以下是笔试面试过程中遇到的关于一些自定义排序规则的题目。可以结合实际场景做下应用。
注：以下只给出大概代码样例，水平有限，不保证完全正确。

1、题目一

（1）：华为通用软件暑期实习笔试4.13场次算法题第一题
题干：硬件资源分配（不花点时间，题干都理不顺.....）
有M台服务器，每台服务器有以下属性：编号、CPU核数（1_{100）、内存、CPU架构（0}8）、是否支持NP加速的标识（0,1）。然后有一个资源分配要求，要求分配N台满足要求的服务器。具体如下：CPU核数>=cpuCount、内存>=memSize、CPU架构=cpuArch、是否支持NP加速=supportNP。其中，cpuCount、memSize、cpuArch、supportNP为这个要求输入的分配参数。
分配时会指定优先级策略，策略如下：
策略1：CPU优先，优先选择CPU核数满足分配要求并且最接近分配要求的cpuCount。如果CPU核数相同，在按内存满足要求并选择最接近memSize的服务器分配。
策略2：内存优先，优先选择内存满足分配要求并且最接近分配要求的memSize。如果内存相同，在按cpu核数满足要求并选择最接近cpuCount的服务器分配
如果两台服务器属性都相同，则按服务器编号从小到大选择（编号不会重复）
输入：
第一行：服务器数量M
接下来M行为M台服务器属性的数组
下一行为分配要求：最大分配数量N，分配策略strategy，cupCount，memSize，cpuArch，supportNP
其中：
1<=M<=1000
1<=N<=1000
strategy：1表示策略1,2表示策略2
1<=cpuCount<=100
10<=memSize<=1000
0<=cpuArch<=8，另外，cpuArch使用9表示所有服务器架构都满足分配要求
0<=supportNP<=1，另外，为2时表示无论是否支持NP加速都满足分配要求
输出
先输出实际分配数量，后按照分配的服务器编号从小到大依次输出，以空格分开
样例1

输入
4
0,2,200,0,1
1,3,400,0,1
2,3,400,1,0
3,3,300,0,1
3 1 3 200 0 1
输出
2 1 3
解释：只有1和3满足要求，要求分配2台服务器，所以结果为2 1 3

样例2

输入
6
0,2,200,0,1
1,4,330,2,1
2,3,400,3,1
3,3,310,1,1
4,3,320,8,1
5,3,330,0,1
3 2 3 300 9 2
（这里注意一下输入的格式，最后一行是空格分开）
输出
3 3 4 5
解释：编号1~5都满足分配要求，按策略2分配即内存优先，内存>=300并且最接近300的服务器编号是3 4 1 5 2。
其中1和5内存相同，然后会比较CPU，即CPU>=3且最接近的，所以5优先于1.因此最后分配的三台服务器是3 4 5。
输出时先输出数量3，再按编号排序输出3 4 5

（2）思路自定义排序：
主要先对一些特殊情况考虑，并且不同的策略不同的排序规则，但是都类似。

inp = list(map(int, input().strip().split(" ")))
N, strategy, cpuCount, memSize, cpuArch, SupportNP = inp
# N, strategy, cpuCount, memSize, cpuArch, SupportNP = 2, 1, 3, 300, 9, 1

res = []
for item in ans:
    if cpuArch != 9 and item[3] != cpuArch:
        continue
    if SupportNP != 2 and item[4] != SupportNP:
        continue
    res.append(item)

if strategy == 1:
    res = list(filter(lambda item: item[1]>=cpuCount and item[2]>=memSize, res))
    # res = list(filter(lambda item: item[2]>=memSize, res))
    res.sort(key=lambda x: (x[1], x[2]))

    if len(res) <= N and len(res) > 0:
        tmp = [len(res)] + sorted([item[0] for item in res])
        print(" ".join([str(i) for i in tmp]))
    elif len(res) > N:
        tmp = [N] + sorted([res[i][0] for i in range(N)])
        print(" ".join([str(i) for i in tmp]))
    else:
        print(0)

elif strategy == 2:
    res = list(filter(lambda item: item[2]>=memSize and item[1]>=cpuCount, res))
    # res = list(filter(lambda item: item[1]>=cpuCount, res))
    res.sort(key=lambda x: (x[2], x[1]))

    if len(res) <= N and len(res) > 0:
        tmp = [len(res)] + sorted([item[0] for item in res])
        print(" ".join([str(i) for i in tmp]))
    elif len(res) > N:
        tmp = [N] + sorted([res[i][0] for i in range(N)])
        print(" ".join([str(i) for i in tmp]))
    else:
        print(0)

2、题目二

（1）、华为通用软件暑期实习业务一面算法题
Leetcode最大数：链接https://leetcode-cn.com/problems/largest-number/
题干：
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
示例：
输入：nums = [3,30,34,5,9]
输出："9534330"
（2）、三种思路
version1：
由于没有看到nums数组的容量范围，第一反应直接全排列，然后对每一种结果作比较。

from itertools import permutations

nums = [3, 30, 34, 5, 9]

res = set(permutations(nums))  # 全排列结果去重
res = [int("".join(list(map(str, item)))) for item in res]  # 结果拼接再类型转换
print(max(res))  # 取最大值 输出 9534330

但是nums这么大范围，使用全排列做得无用功太多了，时间和空间复杂度都不满足。
version2：
维持一个单调队列，队列中的元素拼接之后保证最大，逐个遍历当前元素，再往队列逐个位置尝试插入，并最终找到插入位置保持队列的规则。

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        queue = []
        # 逐个遍历列表元素
        for i in range(len(nums)):
            # 队列为空，直接入队
            if len(queue) == 0:
                queue.append(nums[i])
                continue
            # 假定当前nums[i]放在队尾，拼接后的值为mx
            mx_ind = -1
            mx = int("".join(list(map(str,  queue + [nums[i]]))))
            # 逐个插入队列中，作比较，谁大
            for j in range(len(queue)):
                tmp = int("".join(list(map(str,  queue[:j] + [nums[i]] + queue[j:]))))
                if tmp > mx:
                    mx = tmp
                    mx_ind = j
            # 找到插入位置
            if mx_ind != -1:
                queue = queue[:mx_ind] + [nums[i]] + queue[mx_ind:]
            else:
                queue = queue[:] + [nums[i]]
        # 合并                
        st = "".join(list(map(str, queue)))
        # 去除首部0
        st = st.lstrip("0")
        # 如果全为0，如nums=[0, 0]，则输出0
        if len(st) == 0:
            return "0"
        else:
            return st

执行结果：

version3：
nums中的元素的位置不是由单一的元素决定，而是根据两个元素拼接之后的谁大决定的，如果"xy" > "yx"，那就[x, y]，否则[y, x]。因此可以使用自定义排序。

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        from functools import cmp_to_key
        def func(a, b):
            # 当前两元素长度相等，则按照大小排列
            if len(str(a)) == len(str(b)):
                return b - a
            else:
            # 长度不同，则根据拼接后的大小排序
                return int(str(b)+str(a)) - int(str(a)+str(b)) 
        
        nums = sorted(nums, key=cmp_to_key(func))
        
        # 突然发现这样写更简洁 ，不用额外定义func   
        # nums = sorted(nums, key=cmp_to_key(lambda x, y: int(str(y)+str(x)) - int(str(x)+str(y))))

        s = "".join(list(map(str, nums)))
        s = s.lstrip("0")
        if len(s) != 0:
            return s
        else:
            return "0"

执行结果：

3、题目三

（1）、荣耀通用软件暑期开发实习生笔试第二题
题目记不太清了，大概就是把日志文件中的一行一行记录根据时间戳排序，记录是字符串，不过整个记录中包含其他的一些无用字符串，因此要自己过滤出有用的时间戳。
实例输入：

5 
my/2019-01-01T09:00:01
my/2019-01-01T09:00:01
abc/2018-12-24T08:00:00/test/you
1/2018-12-24T08:00:00/test/Test1
123/2018-12-24T08:00:09/test/me

说明：5表示5行记录
输出：

1/2018-12-24T08:00:00/test/Test1
abc/2018-12-24T08:00:00/test/you
123/2018-12-24T08:00:09/test/me
my/2019-01-01T09:00:01

说明：优先根据时间戳信息排序，时间戳满足一定的格式XXXX-XX-XXTXX:XX:XX，T为分隔符，分割日期和时间，前半部分为日期，后半部分为时间，时间戳相同根据字符串长度排序，如果长度也相同，则按照首字母的ascii码表比较从小到大排序，如果两个记录字符串完全相同，则输出一条即可。
（2）、思路
主要还是自定义排序规则，不过对于所有记录都要做下处理判断是否满足时间戳规则，以及去重
代码如下

from functools import cmp_to_key

# 判断记录字符串是否符合时间戳格式
def is_time_format(s):
    if len(s) != 19:
        return False
    if s[4] != "-"  or s[7] != "-" or s[10] != "T" or s[13] != ":" or s[16] != ":":
        return False
    return True

# 自定义排序规则
def func(a, b):
    if a[0] != b[0]:
        if a[0] > b[0]:
            return 1
        else:
            return -1
    else:
        if len(a[1]) != len(b[1]):
            return len(a[1]) - len(b[1])
        else:
            return ord(a[1][0]) - ord(b[1][0])

# 处理输入
size = int(input().strip())
time_str = []
for _ in range(size):
    # 并将记录分割成列表暂存起来
    tmp = input().strip().split("/")
    time_str.append(tmp)

# 保存满足时间戳的记录
res = []
for i in range(len(time_str)):
    for j in range(len(time_str[i])):
        if is_time_format(time_str[i][j]):
            res.append([time_str[i][j],  "/".join(time_str[i])])
            break
res = sorted(res, key=cmp_to_key(func))  # 自定义排序

# 重塑结果
ans = []
for i in range(len(res)):
    if res[i][1] not in ans:
        ans.append(res[i][1])

# 处理输出
print("\n".join(ans))