# 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']'''
