寫在前面，本文主要介紹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核數（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<=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))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/469889.html
標籤：其他
上一篇：Hello World—— 第一個Python程式，向世界問好（基礎小知識）
下一篇：Volatile的學習