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

2023-08-14 06:27| 来源: 网络整理| 查看: 265

写在前面，本文主要介绍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 __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核数（1100）、内存、CPU架构（08）、是否支持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 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))

【本文地址】

公司简介

联系我们