多关键字如何排序
场景：员工表按照薪资排序，薪资相同的按照年龄排序
尝试：先按照薪资排序(升序)，再按照年龄排序(升序)
#（薪资,年龄）
(5000,28)，(6000,28)，(5000,26)，(6000,26)
# 按照薪资排序（稳定排序，薪资相同保持原来的先后顺序）
(5000,28)，(5000,26)，(6000,28)，(6000,26)
#再按照年龄排序（稳定排序，年龄相同保持原来的先后顺序）
(5000,26)，(6000,26)，(5000,28)，(6000,28)
尝试：先按照年龄排序，再按照薪资排序
#（薪资,年龄）
(5000,28)，(6000,28)，(5000,26)，(6000,26)
#按照年龄排序（稳定排序）
(5000,26)，(6000,26)，(5000,28)，(6000,28)
#按照薪资排序（稳定排序）
(5000,26)，(5000,28)，(6000,26)，(6000,28)
总结：多关键字排序从低关键字先排序，所有关键字排序要保证是稳定排序
两位数正整数排序
按照十位升序，十位相同的按照个位升序。可以套用多关键字排序，先按照个位稳定排序，再按照十位稳定排序。
多位正整数排序
根据两位数的示例，可以先排个位，再排十位，再排百位...
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取个位，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]
时间复杂度
def radix_sort(li):
max_num = max(li)
i = 0
while 10 ** i <= max_num:#和最大值的位数有关
... #所有数放到buckets再取出来，复杂度O(n)
最大值位数k，需要排序的数量n，复杂度O(kn)
局限性
不支持小数、字符串排序。如果是负数可以考虑找出最小的负数，所有数加上最小负数的绝对值变成正数后再排序，输出时再统一减去最小负数的绝对值。
