多關(guān)鍵字如何排序
場(chǎng)景：?jiǎn)T工表按照薪資排序脚牍，薪資相同的按照年齡排序
嘗試：先按照薪資排序(升序)掰伸，再按照年齡排序(升序)
#（薪資,年齡）
(5000,28)晋控，(6000,28)损趋，(5000,26)，(6000,26)
# 按照薪資排序（穩(wěn)定排序元咙，薪資相同保持原來的先后順序）
(5000,28)，(5000,26)巫员，(6000,28)庶香，(6000,26)
#再按照年齡排序（穩(wěn)定排序，年齡相同保持原來的先后順序）
(5000,26)简识，(6000,26)赶掖，(5000,28)，(6000,28)
嘗試：先按照年齡排序七扰，再按照薪資排序
#（薪資,年齡）
(5000,28)奢赂，(6000,28)，(5000,26)颈走，(6000,26)
#按照年齡排序（穩(wěn)定排序）
(5000,26)呈驶，(6000,26)，(5000,28)疫鹊，(6000,28)
#按照薪資排序（穩(wěn)定排序）
(5000,26)袖瞻，(5000,28)，(6000,26)拆吆，(6000,28)
總結(jié)：多關(guān)鍵字排序從低關(guān)鍵字先排序聋迎，所有關(guān)鍵字排序要保證是穩(wěn)定排序
兩位數(shù)正整數(shù)排序
按照十位升序，十位相同的按照個(gè)位升序枣耀∶乖危可以套用多關(guān)鍵字排序，先按照個(gè)位穩(wěn)定排序捞奕，再按照十位穩(wěn)定排序牺堰。
多位正整數(shù)排序
根據(jù)兩位數(shù)的示例，可以先排個(gè)位颅围，再排十位伟葫，再排百位...
def radix_sort(li):
max_num = max(li)
i = 0
while 10 ** i <= max_num:#通過10^i方式得到最大值有幾位
buckets = [[] for _ in range(10)]
for val in li:
digit = val // (10 ** i) % 10#i=0取個(gè)位，i=1取十位院促，i=2取百位...
buckets[digit].append(val)
li.clear()
for bucket in buckets:
li.extend(bucket)
i += 1
li = [10,5,9528,288,12]
radix_sort(li)
print(li)
>>>[5, 10, 12, 288, 9528]
時(shí)間復(fù)雜度
def radix_sort(li):
max_num = max(li)
i = 0
while 10 ** i <= max_num:#和最大值的位數(shù)有關(guān)
... #所有數(shù)放到buckets再取出來筏养，復(fù)雜度O(n)
最大值位數(shù)k，需要排序的數(shù)量n常拓，復(fù)雜度O(kn)
局限性
不支持小數(shù)渐溶、字符串排序。如果是負(fù)數(shù)可以考慮找出最小的負(fù)數(shù)弄抬，所有數(shù)加上最小負(fù)數(shù)的絕對(duì)值變成正數(shù)后再排序茎辐，輸出時(shí)再統(tǒng)一減去最小負(fù)數(shù)的絕對(duì)值。
