寫在前面，本文主要介紹Python基礎(chǔ)排序和自定義排序的一些規(guī)則，如果都比較熟悉，可以直接翻到第三節(jié)，看下實(shí)際的筆試面試題中關(guān)于自定義排序的應(yīng)用。

創(chuàng)新互聯(lián)，專注為中小企業(yè)提供官網(wǎng)建設(shè)、營(yíng)銷型網(wǎng)站制作、響應(yīng)式網(wǎng)站建設(shè)、展示型網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)等服務(wù)，幫助中小企業(yè)通過(guò)網(wǎng)站體現(xiàn)價(jià)值、有效益。幫助企業(yè)快速建站、解決網(wǎng)站建設(shè)與網(wǎng)站營(yíng)銷推廣問(wèn)題。

一、基礎(chǔ)排序

排序是比較基礎(chǔ)的算法，與很多語(yǔ)言一樣，Python也提供了對(duì)列表的排序方法和內(nèi)建排序函數(shù)。

1、兩種排序方式

方式一：

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

方式二：

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

兩種方式都可以實(shí)現(xiàn)對(duì)列表元素的排序，從接受參數(shù)更能看出兩者區(qū)別和相同點(diǎn)。

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

2、不同點(diǎn)

（1）：sort()屬于列表對(duì)象特有的排序方法，因此調(diào)用方法直接在列表本身進(jìn)行修改，返回值為None或者說(shuō)無(wú)需返回值。
（2）： sorted()屬于python提供內(nèi)建函數(shù)，無(wú)需導(dǎo)入可直接用，而從接受對(duì)象來(lái)看，sorted()方法可以直接接受iterable可迭代對(duì)象，因此作用對(duì)象更廣泛，包括字符串，元組甚至字典都可以，返回一個(gè)列表，如下所示

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作為排序結(jié)果返回

（3）：對(duì)于Python3.x中的sort()無(wú)法函數(shù)自定義排序規(guī)則后面會(huì)說(shuō)到。

3、相同點(diǎn)

（1）：都支持reverse反轉(zhuǎn)操作，參數(shù)reverse接收布爾類型，比如reverse=True，則表示排序結(jié)果逆序。

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

（2）： 都支持關(guān)鍵函數(shù)排序，也就是key參數(shù)指定排序規(guī)則，參數(shù)的接收值為一個(gè)函數(shù)，該函數(shù)可以接收一個(gè)參數(shù)并返回一個(gè)值用來(lái)比較，如下，len接收字符串，返回長(zhǎng)度作為比較值。

test_string = "Hello World Welcome to My City"
print(sorted(test_string.split(" "), key=len)) # 根據(jù)字符串長(zhǎng)度排序
# 輸出：['to', 'My', 'City', 'Hello', 'World', 'Welcome']
print(sorted(test_string.split(" "), key=str.lower)) # 根據(jù)小寫之后的字典序排序 
# 輸出：['City', 'Hello', 'My', 'to', 'Welcome', 'World']

test_list = [-5, 4, 0, 2, 1]
print(sorted(test_list, key=abs)) # 根據(jù)絕對(duì)值排序
# 輸出：[0, 1, 2, 4, -5]

（3）：更廣泛的可以使用lambda表達(dá)式來(lái)完成更復(fù)雜排序。如下對(duì)二維列表多級(jí)排序

li = [
    [3 ,5],
    [5 ,0],
    [5 ,6],
    [3 ,-1],
    [2, 9]
]
# 多級(jí)排序
# 根據(jù)第一個(gè)元素從小打到排列，當(dāng)?shù)谝粋€(gè)元素相等，按照第二個(gè)元素從大到小排列
li.sort(key=lambda x: (x[0], -x[1])) 
print(li)
#  輸出 [[2, 9], [3, 5], [3, -1], [5, 6], [5, 0]]

也或者可以根據(jù)復(fù)雜對(duì)象的某些屬性排序。對(duì)對(duì)象根據(jù)屬性進(jìn)行排序

# 學(xué)生對(duì)象，包括年齡，身高體重等
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)

# 班級(jí)里有很多學(xué)生
classes = [s1, s2, s3, s4, s5]
# 根據(jù)學(xué)生的年齡排序
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

從以上排序結(jié)果中相同年齡的學(xué)生還保持排序前的相對(duì)順序，說(shuō)明sort()排序也是穩(wěn)定排序，sort()底層是基于合并排序和插入排序集合的一種更高效排序算法。以上是使用lambda表達(dá)式指定排序規(guī)則，也可以使用operator中提供的其他更加簡(jiǎn)潔的方式。

# 同樣適用上述的Student例子
from operator import itemgetter, attrgetter

# 實(shí)現(xiàn)根據(jù)學(xué)生年齡排序
print(sorted(classes, key=attrgetter('age')))
print(sorted(classes, key=itemgetter(1)))
# 實(shí)現(xiàn)多級(jí)排序 新根據(jù)身高，再根據(jù)年齡排序
sorted(classes, key=attrgetter('height', 'age'))

二、排序進(jìn)階

其他語(yǔ)言中普遍提供的有cmp函數(shù)，也就是自定義更高級(jí)函數(shù)作為排序規(guī)則。而在python3.x中sort()不在支持cmp自定義函數(shù)比較，想要使用cmp，則需要是使用sorted()，并額外的做一些包裝。

1、舉例

比如，同樣使用如上的Student例子，想要完成自定義排序規(guī)則，比如首先按照年齡大小排序，當(dāng)年齡相同的時(shí)候按照體重逆序排序，如果體重也相同則按照身高逆序排序。

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)

# 班級(jí)有7個(gè)學(xué)生
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))
    
輸出結(jié)果
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

對(duì)于sorted(iterable, key=lambda x:x)，這種比較傾向于待排序的每個(gè)元素都有一個(gè)絕對(duì)的大小值作為排序標(biāo)準(zhǔn)，而有時(shí)候會(huì)絕對(duì)大小是根據(jù)兩個(gè)元素才能得出的衡量，因此可以使用如上functools.cmp_to_key構(gòu)建多個(gè)元素的比較函數(shù)。cmp_to_key包裝后的自定義比較函數(shù)可以接受兩個(gè)元素，將兩個(gè)元素的對(duì)比結(jié)果作為返回值，另外注意，自定義的比較函數(shù)返回值需要是整型。

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，并在內(nèi)部定義一個(gè)K類并返回這個(gè)K類，這個(gè)類內(nèi)部完成了各種比較運(yùn)算符的重載（也就是mycmp的定義的排序規(guī)則），這個(gè)類是可調(diào)用的，在參與比較的時(shí)候其實(shí)是K的對(duì)象，而在使用lambda匿名表達(dá)式的時(shí)候使用是列表中的元素進(jìn)行大小比較。如下：

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

三、真題

以下是筆試面試過(guò)程中遇到的關(guān)于一些自定義排序規(guī)則的題目?？梢越Y(jié)合實(shí)際場(chǎng)景做下應(yīng)用。
注：以下只給出大概代碼樣例，水平有限，不保證完全正確。

1、題目一

（1）：華為通用軟件暑期實(shí)習(xí)筆試4.13場(chǎng)次算法題第一題
題干：硬件資源分配（不花點(diǎn)時(shí)間，題干都理不順.....）
有M臺(tái)服務(wù)器，每臺(tái)服務(wù)器有以下屬性：編號(hào)、CPU核數(shù)（1_{100）、內(nèi)存、CPU架構(gòu)（0}8）、是否支持NP加速的標(biāo)識(shí)（0,1）。然后有一個(gè)資源分配要求，要求分配N臺(tái)滿足要求的服務(wù)器。具體如下：CPU核數(shù)>=cpuCount、內(nèi)存>=memSize、CPU架構(gòu)=cpuArch、是否支持NP加速=supportNP。其中，cpuCount、memSize、cpuArch、supportNP為這個(gè)要求輸入的分配參數(shù)。
分配時(shí)會(huì)指定優(yōu)先級(jí)策略，策略如下：
策略1：CPU優(yōu)先，優(yōu)先選擇CPU核數(shù)滿足分配要求并且最接近分配要求的cpuCount。如果CPU核數(shù)相同，在按內(nèi)存滿足要求并選擇最接近memSize的服務(wù)器分配。
策略2：內(nèi)存優(yōu)先，優(yōu)先選擇內(nèi)存滿足分配要求并且最接近分配要求的memSize。如果內(nèi)存相同，在按cpu核數(shù)滿足要求并選擇最接近c(diǎn)puCount的服務(wù)器分配
如果兩臺(tái)服務(wù)器屬性都相同，則按服務(wù)器編號(hào)從小到大選擇（編號(hào)不會(huì)重復(fù)）
輸入：
第一行：服務(wù)器數(shù)量M
接下來(lái)M行為M臺(tái)服務(wù)器屬性的數(shù)組
下一行為分配要求：最大分配數(shù)量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表示所有服務(wù)器架構(gòu)都滿足分配要求
0<=supportNP<=1，另外，為2時(shí)表示無(wú)論是否支持NP加速都滿足分配要求
輸出
先輸出實(shí)際分配數(shù)量，后按照分配的服務(wù)器編號(hào)從小到大依次輸出，以空格分開
樣例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臺(tái)服務(wù)器，所以結(jié)果為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
解釋：編號(hào)1~5都滿足分配要求，按策略2分配即內(nèi)存優(yōu)先，內(nèi)存>=300并且最接近300的服務(wù)器編號(hào)是3 4 1 5 2。
其中1和5內(nèi)存相同，然后會(huì)比較CPU，即CPU>=3且最接近的，所以5優(yōu)先于1.因此最后分配的三臺(tái)服務(wù)器是3 4 5。
輸出時(shí)先輸出數(shù)量3，再按編號(hào)排序輸出3 4 5

（2）思路自定義排序：
主要先對(duì)一些特殊情況考慮，并且不同的策略不同的排序規(guī)則，但是都類似。

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）、華為通用軟件暑期實(shí)習(xí)業(yè)務(wù)一面算法題
Leetcode最大數(shù)：鏈接https://leetcode-cn.com/problems/largest-number/
題干：
給定一組非負(fù)整數(shù)nums，重新排列每個(gè)數(shù)的順序（每個(gè)數(shù)不可拆分）使之組成一個(gè)最大的整數(shù)。
示例：
輸入：nums = [3,30,34,5,9]
輸出：""
（2）、三種思路
version1：
由于沒有看到nums數(shù)組的容量范圍，第一反應(yīng)直接全排列，然后對(duì)每一種結(jié)果作比較。

from itertools import permutations

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

res = set(permutations(nums))  # 全排列結(jié)果去重
res = [int("".join(list(map(str, item)))) for item in res]  # 結(jié)果拼接再類型轉(zhuǎn)換
print(max(res))  # 取最大值 輸出 

但是nums這么大范圍，使用全排列做得無(wú)用功太多了，時(shí)間和空間復(fù)雜度都不滿足。
version2：
維持一個(gè)單調(diào)隊(duì)列，隊(duì)列中的元素拼接之后保證最大，逐個(gè)遍歷當(dāng)前元素，再往隊(duì)列逐個(gè)位置嘗試插入，并最終找到插入位置保持隊(duì)列的規(guī)則。

classSolution:
deflargestNumber(self,nums:List[int])->str:
queue=[]
        # 逐個(gè)遍歷列表元素
foriinrange(len(nums)):
            # 隊(duì)列為空，直接入隊(duì)
iflen(queue)==0:
queue.append(nums[i])
continue
            # 假定當(dāng)前nums[i]放在隊(duì)尾，拼接后的值為mx
mx_ind=-1
mx=int("".join(list(map(str,queue+[nums[i]]))))
            # 逐個(gè)插入隊(duì)列中，作比較，誰(shuí)大
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

執(zhí)行結(jié)果：

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

classSolution:
deflargestNumber(self,nums:List[int])->str:
fromfunctoolsimportcmp_to_key
deffunc(a,b):
            # 當(dāng)前兩元素長(zhǎng)度相等，則按照大小排列
iflen(str(a))==len(str(b)):
returnb-a
else:
            # 長(zhǎng)度不同，則根據(jù)拼接后的大小排序
returnint(str(b)+str(a))-int(str(a)+str(b))

nums=sorted(nums,key=cmp_to_key(func))
        
        # 突然發(fā)現(xiàn)這樣寫更簡(jiǎn)潔 ，不用額外定義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"

執(zhí)行結(jié)果：

3、題目三

（1）、榮耀通用軟件暑期開發(fā)實(shí)習(xí)生筆試第二題
題目記不太清了，大概就是把日志文件中的一行一行記錄根據(jù)時(shí)間戳排序，記錄是字符串，不過(guò)整個(gè)記錄中包含其他的一些無(wú)用字符串，因此要自己過(guò)濾出有用的時(shí)間戳。
實(shí)例輸入：

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

說(shuō)明：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

說(shuō)明：優(yōu)先根據(jù)時(shí)間戳信息排序，時(shí)間戳滿足一定的格式XXXX-XX-XXTXX:XX:XX，T為分隔符，分割日期和時(shí)間，前半部分為日期，后半部分為時(shí)間，時(shí)間戳相同根據(jù)字符串長(zhǎng)度排序，如果長(zhǎng)度也相同，則按照首字母的ascii碼表比較從小到大排序，如果兩個(gè)記錄字符串完全相同，則輸出一條即可。
（2）、思路
主要還是自定義排序規(guī)則，不過(guò)對(duì)于所有記錄都要做下處理判斷是否滿足時(shí)間戳規(guī)則，以及去重
代碼如下

from functools import cmp_to_key

# 判斷記錄字符串是否符合時(shí)間戳格式
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

# 自定義排序規(guī)則
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):
    # 并將記錄分割成列表暫存起來(lái)
    tmp = input().strip().split("/")
    time_str.append(tmp)

# 保存滿足時(shí)間戳的記錄
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))  # 自定義排序

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

# 處理輸出
print("\n".join(ans))

文章題目：Python自定義排序及實(shí)際遇到的一些實(shí)例
URL標(biāo)題：http://chinadenli.net/article26/dsogpcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、云服務(wù)器、網(wǎng)站制作、定制開發(fā)、服務(wù)器托管、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)