目录
一:基排序的思想
二:Python代码实现
三:算法性能分析
一:基排序的思想
将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。基数排序的方式可以采用 LSD(Least significant digital)或 MSD(Most significant digital),LSD 的排序方式由键值的最右边开始,而 MSD 则相反,由键值的最左边开始。
二:Python代码实现
def radix_sort(alist):
"""基排序"""
i = 0 # 控制待排序的位数
n = 1 # 最小的位数置为1(包含0)
max_num = max(alist) # 得到带排序数组中最大数
while max_num > 10**n: # 得到最大数是几位数
n += 1 # 最大是n位数
while i < n:
bucket = {} # 用字典构建桶
for x in range(10): # 为什么是10、应为是十进制的书
bucket.setdefault(x, []) # 将每个桶置空
# {0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: [], 9: []}
for x in alist: # 对每一位进行排序
radix =int((x / (10**i)) % 10) # 得到每位的基数
bucket[radix].append(x) # 将对应的数组元素加入到相应位基数的桶中
j = 0
for k in range(10):
if len(bucket[k]) != 0: # 若桶不为空
for y in bucket[k]: # 将该桶中每个元素
alist[j] = y # 放回到数组中
j += 1
# print(alist)
i += 1
if __name__ == '__main__':
alist = [12, 3, 45, 3543, 214, 1, 214, 4553, 234567]
print(alist)
radix_sort(alist)
print(alist)
三:算法性能分析