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]
輸出：""
（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))  # 取最大值 輸出 

但是nums這么大范圍，使用全排列做得無用功太多了，時間和空間復雜度都不滿足。
version2：
維持一個單調隊列，隊列中的元素拼接之后保證最大，逐個遍歷當前元素，再往隊列逐個位置嘗試插入，并最終找到插入位置保持隊列的規則。

classSolution:
deflargestNumber(self,nums:List[int])->str:
queue=[]
        # 逐個遍歷列表元素
foriinrange(len(nums)):
            # 隊列為空，直接入隊
iflen(queue)==0:
queue.append(nums[i])
continue
            # 假定當前nums[i]放在隊尾，拼接后的值為mx
mx_ind=-1
mx=int("".join(list(map(str,queue+[nums[i]]))))
            # 逐個插入隊列中，作比較，誰大
forjinrange(len(queue)):
tmp=int("".join(list(map(str,queue[:j]+[nums[i]]+queue[j:]))))
iftmp>mx:
mx=tmp
mx_ind=j
            # 找到插入位置
ifmx_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
iflen(st)==0:
return"0"
else:
returnst

執行結果：

version3：
nums中的元素的位置不是由單一的元素決定，而是根據兩個元素拼接之后的誰大決定的，如果"xy" > "yx"，那就[x, y]，否則[y, x]。因此可以使用自定義排序。

classSolution:
deflargestNumber(self,nums:List[int])->str:
fromfunctoolsimportcmp_to_key
deffunc(a,b):
            # 當前兩元素長度相等，則按照大小排列
iflen(str(a))==len(str(b)):
returnb-a
else:
            # 長度不同，則根據拼接后的大小排序
returnint(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(lambdax,y:int(str(y)+str(x))-int(str(x)+str(y))))

s="".join(list(map(str,nums)))
s=s.lstrip("0")
iflen(s)!=0:
returns
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))

文章題目：Python自定義排序及實際遇到的一些實例
URL標題：http://m.kartarina.com/article26/dsogpcg.html

成都網站建設公司_創新互聯，為您提供搜索引擎優化、云服務器、網站制作、定制開發、服務器托管、靜態網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯