排序算法(七)之基排序(Python代码实现)

mac2025-01-29  22

目录

一:基排序的思想

二: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)

三:算法性能分析

 

最新回复(0)