排序算法（6）——基数排序
基数排序
概念：
通过元素的部分要素，将要排序的元素分配至某些“桶”中，以此达到排序的作用。比如为整数排序，依次用整数的个位、十位...来排序（LSD低位优先）；或者高位到低位依次排序（MSD高位优先）。
算法步骤：
首先初始化10个桶(固定的)，桶下标为0-9。
按LSD就是按个位数大小排好放入桶内，然后在此基础上排十位，以此类推，直到遍历完最高位次。
每一次排完都要把桶内元素还原回原数组中。
图源：https://www.runoob.com/w3cnote/radix-sort.html
算法复杂度：
时间复杂度----平均： O(n*k) | 最坏：O(n*k) | 最好：O(n*k)
空间复杂度----O(n+k)（n为元素个数，k表示最大整数由几位数构成）
稳定性----稳定
实例：
def radix_sort(ls):i = 0 # 记录当前正在排哪一位，最低位为1max_num = max(ls) # 最大值j = len(str(max_num)) # 记录最大值的位数while i < j:bucket_list =[[] for q in range(10)] #初始化桶数组for x in ls:bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组ls.clear()for x in bucket_list: # 放回原序列for y in x:ls.append(y)i += 1return lsif __name__ == '__main__':list1 = [34, 231, 74, 5, 98, 34, 18, 88, 147, 51, 65, 75, 144, 89]sort_list = radix_sort(list1)print(sort_list)
以上第一次按个位排序放入桶中是：
[[], [231, 51], [], [], [34, 74, 34, 144], [5, 65, 75], [], [147], [98, 18, 88], [89]]第二次按十位排序：
[[5], [18], [], [231, 34, 34], [144, 147], [51], [65], [74, 75], [88, 89], [98]]第三次按百位排序：
[[5, 18, 34, 34, 51, 65, 74, 75, 88, 89, 98], [144, 147], [231], [], [], [], [], [], [], []]最后还原回原列表就排好了：
[5, 18, 34, 34, 51, 65, 74, 75, 88, 89, 98, 144, 147, 231]以上若描述有误，还请留言指出，谢谢！