插入\交換\選擇\歸并類的排序算法都需要通過比較關鍵字的大小來完成排序.因為存在兩兩比較所以這一類的排序方法在最好情況下能達到的復雜度是O(n*logn),如快速排序\堆排序\歸并排序.在一般情況下和最壞情況下復雜度更是達到O(n**2).
為了降低復雜度,就有牛人想出了分配收集排序方法,稍后分析它的時間復雜度能到達O(n),
而基數排序就是一種典型的搜集分配收集排序方法.基數排序時一種借助于多關鍵字排序的思想對單關鍵字排序的方法.其基本思想是通過對排序記錄進行若干趟(有幾個關鍵字就幾趟)"分配"與"收集"來實現排序.
如:
1. 對整數排序,建立編號0-9(10進制的基數)10個桶,用于裝對應位為編號的記錄.先將待排序序列分配按'個位'數字分配到10各桶中,然后將桶按從小到大的順序串接起來.
2.將上一步的結果再按'十位''數字分配到10各桶中,然后將桶按從小到大的順序串接起來.
3. 將上一步的結果再按'百位''數字分配到10各桶中,然后將桶按從小到大的順序串接起來.
4.如果還有千位\萬位.重復以上步驟,直到完成最高位的分配與收集,排序結束.
動圖示例:(轉自菜鳥教程:1.10 基數排序 | 菜鳥教程 (runoob.com))
# 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)
將一個列表作為輸入,將每一個記錄處理為具有相同位數的字符串(用字符串類型時為了方便處理)
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的方式轉化為一樣的長度
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
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']'''
1)時間復雜度
對于n個記錄(假設每個記錄含d個關鍵字,每個關鍵字的取值范圍為rd個值)進行鏈式基數排序時,每一趟分配的時間復雜度為O(n),每一趟收集的時間復雜度為O(rd),整個排序需進行d趟分配和收集,所以時間復雜度為O(d(n+rd))。
(2)空間復雜度
所需輔助空間為2rd個隊列指針,另外由于需用鏈表做存儲結構,則相對于其他以順序結構存儲記錄的排序方法而言,還增加了n個指針域的空間,所以空間復雜度為O(n+rd)。
(1)是穩定排序。
(2)可用于鏈式結構,也可用于順序結構。
(3)時間復雜度可以突破基于關鍵字比較一類方法的下界O(nlog2n),達到O(n)。
(4)基數排序使用條件有嚴格的要求:需要知道各級關鍵字的主次關系和各級關鍵字的取值范圍。
1.嚴蔚敏等數據結構C語言版(第二版)>>
2.Bradley N. Miller, David L. Ranum Introduction to Data Structures and Algorithms in Python>>
到此這篇關于python之基數排序的實現的文章就介紹到這了,更多相關python之基數排序內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家!