# Bradley N. Miller, David L. Ranum# Introduction to Data Structures and Algorithms in Python# Copyright 2005# #queue.py class Queue: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self, item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items)
2.处理输入数据
将一个列表作为输入,将每一个记录处理为具有相同位数的字符串(用字符串类型时为了方便处理)
def inDataProcess(lis): max_lengh = max([len(lis[i]) for i in range(len(lis))]) # 查询记录中最长的字符串 return [x.zfill(max_lengh) for x in lis] # 将每一个记录都通过添加前导0的方式转化为一样的长度
3.基数排序主函数
def radixSort(seq:list): source_data = inDataProcess(seq) # 输入处理 res = [] # 用于保存结果列表 big_queue = Queue() # 用于转化的队列 for ele in source_data: big_queue.enqueue(ele) for i in range(len(source_data[0])-1,-1,-1): buckets = [] # 用于保存每一趟的10各基数桶 for num in range(10): # 建立10个基数桶 bucket = Queue() buckets.append(bucket) # 在基数桶中插入数据 while not big_queue.isEmpty(): currentEle = big_queue.dequeue() # 大队列中出队一个元素 index = int(currentEle[i]) # 根据元素对应位上的值添加进对应的基数桶中 buckets[index].enqueue(currentEle) # 把基数桶串联起来 new_big_queue = Queue() for bucket in buckets: while not bucket.isEmpty(): out = bucket.dequeue() new_big_queue.enqueue(out) # print(new_big_queue.size()) # 修改big_queue big_queue = new_big_queue # 将大队列中的元素保存到结果列表中 while not big_queue.isEmpty(): res.append(big_queue.dequeue().lstrip('0')) # 利用lstrip('0')去掉前导0 return res
4.测试及结果
if __name__ == '__main__': lis = [20,101,39,431,58,600,8,4,999,634,157,199,208,138,389,691,400,932,856,843,401,923] lis = [str(i) for i in lis] print(radixSort(lis)) ''' 结果>>>['4', '8', '20', '39', '58', '101', '138', '157', '199', '208', '389', '400', '401', '431', '600', '634', '691', '843', '856', '923', '932', '999']'''
