（九）Python面试之：排序中的艺术

您所在的位置：网站首页 › 列表升序排序python › （九）Python面试之：排序中的艺术

（九）Python面试之：排序中的艺术

2023-04-20 18:40| 来源: 网络整理| 查看: 265

今天主要是总结在python中排序有可能出现的面试题；分为每个小题渐进式、由浅至深进行概述，最后进行总结；该节是关于python中的排序知识总结，排序小编会持续的更新，如感兴趣可以关注收藏。

（一）、sort与sorted的区别

sort是list的排序方法，而且是对该list进行排序，对list值进行了修改；sorted会返回排序后新的list；

In [56]: x = [1, 8, 5, 4] In [57]: x.sort() In [58]: x Out[58]: [1, 4, 5, 8] In [63]: x = [1, 8, 5, 4] In [64]: y = sorted(x) In [65]: y Out[65]: [1, 4, 5, 8]

（二）、使用lambda函数对[-5, 9, 0, 4, -9]排序，得到[-9, -5, 0, 4, 9]

本质是使用了sorted函数，进一步使用key值的排序规则，排序规则往往使用lambda函数；

In [66]: foo = [-5, 9, 0, 4, -9] In [67]: sorted(foo, key=lambda x:x) Out[67]: [-9, -5, 0, 4, 9]

（三）、使用lambda函数对[-5, 9, 0, 4, -9]排序，按照绝对值大小进行排序，如果绝对值相同，则按照正数在前，负数在后

lambda表达式中可以通过tuple的传递方式，生成多个规则，按照规则的顺序，进行规则设定，那么就可以设定lambda x:(abs(x), -x)，这里优先使用绝对值大小，绝对值一样的，按照-x排序，即倒序排序，就可以将9放在前面，-9放在后面；

In [66]: foo = [-5, 9, 0, 4, -9] In [68]: sorted(foo, key=lambda x:(abs(x), -x)) Out[68]: [0, 4, -5, 9, -9]

当然可以设定排序，首先负数在前，正数在后，然后按照绝对值大小，则修改为：

In [66]: foo = [-5, 9, 0, 4, -9] In [69]: sorted(foo, key=lambda x:(x, abs(x))) Out[69]: [-9, -5, 0, 4, 9]

（四）、按照奇偶数排序

使用lambda函数对[-5, 9, 0, 4, -9]排序，奇偶数排序，奇数排前面，偶数排后面；

In [66]: foo = [-5, 9, 0, 4, -9] In [75]: sorted(foo, key=lambda x:(x % 2 == 0)) Out[75]: [-5, 9, -9, 0, 4]

上述的结果从三个方面进行分析：

a、这里只有一个规则，但是我也可以使用tuple进行传递；

b、这里可能大家好奇为什么x%2==0的规则为什么会偶数还在后面呢，其实是因为list的值执行x%2==0的结果为[False, False, True, True, False]，所以默认升序排序，False的值为0，True的值为1，所以排序后就为[-5, 9, -9, 0, 4]；

c、上述结果可以看到，当传入一个规则，如果没有额外的规则，只会按照表达式后的结果进行排序，比如True与False的比较，但可以看到，多个相同True或者False的时候，就按照原来数值的先后顺序了。

这里可以设置更复杂的排序逻辑：1、奇数排前面，偶数排后面；2、然后按照绝对值大小升序；3、绝对值相同的逆序；

In [66]: foo = [-5, 9, 0, 4, -9] In [76]: sorted(foo, key=lambda x:(x % 2 == 0, abs(x), -x)) Out[76]: [-5, 9, -9, 0, 4]

（五）、按照字符串长度进行排序

请对以下列表进行排序，排序的规则是根据其字符串的长度，进行升序排序；这里没什么好讲的，与(三)中的逻辑设定的原理比较类同

In [124]: a = ['a', 'aaa', 'aa'] In [125]: sorted(a, key=lambda x:len(x)) Out[125]: ['a', 'aa', 'aaa']

（六）、按照多列规则排序（多列排序）

例如学生成绩通过score关键字表示，名字通过name关键字表示；请按照成绩降序排序，相同成绩的按照名字升序排序；[{'name':'alice', 'score':38}, {'name':'bob', 'score':18}, {'name':'darl', 'score':28}, {'name':'christ', 'score':28}]

这里可以理解为多列排序，包含多列关键字信息，假如元素为字典，可以通过tuple传入，按照顺序传入键值，如果元素为多维的list，则可以按照(x[0], x[1])进行设计；

In [77]: dl = [{'name':'alice', 'score':38}, {'name':'bob', 'score':18}, {'name':'darl', 'score':28}, {'name':'christ', 'score':28}] In [78]: sorted(dl, key=lambda x:(x['score'], x['name'])) #假如是按照得分逆序，只需加负号，(-x['score'], x['name']) Out[78]: [{'name': 'bob', 'score': 18}, {'name': 'christ', 'score': 28}, {'name': 'darl', 'score': 28}, {'name': 'alice', 'score': 38}]

（七）、字典排序

对字典按照key值进行逆序排序；

In [88]: a={'a':1,'c':3, 'b':2} In [89]: dict(sorted(a.items(), key=lambda x:x[0],reverse=True)) Out[89]: {'c': 3, 'b': 2, 'a': 1}

a、这里对字典排序稍微特殊，sorted中排序对象为可迭代，a.items()实际为key值与value值组成的迭代对象， dict_items([('a', 1), ('c', 3), ('b', 2)])，也可以换成以下写法：

In [91]: a={'a':1,'c':3, 'b':2} In [92]: dict(sorted(zip(a.keys(), a.values()), key=lambda x:x[0],reverse=True)) Out[92]: {'c': 3, 'b': 2, 'a': 1}

b、为什么key不能设定为x.key()，实际字典的迭代对象值只为key，即当前例子是字符串，所以传入的迭代元素无法使用x.key()；

In [93]: [x for x in a] Out[93]: ['a', 'c', 'b']

c、当然上述的lambda函数选择的答案并不是唯一，也可以还有其他解法（字典推导式）；

In [97]: {k:a[k] for k in sorted(a, reverse=True)}#推导式，按照字典的key进行排序 Out[97]: {'c': 3, 'b': 2, 'a': 1} #但此时如果按照value进行排序就不好排序了因为难生成映射

（八）、不用sort与sorted函数实现排序

当然不考虑时间复杂度以及空间复杂度，直观就可以通过新建一个空列表，然后每次append原数组中最小值，需要原数组将每次最小值remove掉；

In [163]: x = [1, 9, 7, 3, 0] In [164]: res = [] In [165]: for i in range(len(x)): ...: res.append(min(x)) ...: x.remove(min(x)) ...: In [166]: res Out[166]: [0, 1, 3, 7, 9]

（九）、求list次大值

方法一：通过排序，set集合防止最大值重复；

In [60]: x = [-1, -1, 9, 9, 8, 5] In [61]: sorted(list(set(x)))[-2] Out[61]: 8

方法二：通过set+remove最大值，再求max；

In [80]: x = [-1, -1, 9, 9, 8, 5] In [81]: y = list(set(x)) In [82]: y.remove(max(y)) In [83]: max(y) Out[83]: 8

方法三：可编写自定义函数

思路可以设定两个变量maxv与sv，分别记录循环遍历得到的最大值与次大值；

1、如果当前元素大于最大值，那么更新次大值sv为上次的最大值，同时也更新最大值maxv；

2、如果当前元素等于最大值，maxv与sv均不需要更新；

3、如果当前元素小于最大值，大于次大值，则将sv次大值更新为当前值；

4、当前元素小于等于次大值，sv与maxv不需要更新；

def secondmax(x): if len(x) maxv: sv = maxv maxv = v elif maxv > v > sv: sv = v if sv == maxv: return None #比如list所有元素均相等时[-1, -1, -1],sv不存在 return sv In [10]: x = [-1, -1, 9, 9, 8, 5] In [11]: secondmax(x) Out[11]: 8

总结：

1、使用sorted函数，最重要是排序规则与lambda函数的结合，lambda巧妙使用可以完成更复杂的排序设计；

2、lambda x:(abs(x), -x...)排序的lambda表达式可以通过tuple传入设计更复杂的规则；

3、字典排序需要注意迭代对象是key值，而非key与value的组合；可以采用items来形成key与value的迭代对象，也可以使用zip(a.keys(), a.values())，当然也可以通过字典推导式解答；

【本文地址】

公司简介

联系我们