主頁 > 知識庫 > python之基數(shù)排序的實現(xiàn)

python之基數(shù)排序的實現(xiàn)

熱門標簽:南昌地圖標注 百應(yīng)電話機器人總部 電梯新時達系統(tǒng)外呼顯示e 西青語音電銷機器人哪家好 地圖標注與注銷 無錫智能外呼系統(tǒng)好用嗎 成都呼叫中心外呼系統(tǒng)哪家強 旅游廁所地圖標注怎么弄 宿州電話機器人哪家好

算法思想

        插入\交換\選擇\歸并類的排序算法都需要通過比較關(guān)鍵字的大小來完成排序.因為存在兩兩比較所以這一類的排序方法在最好情況下能達到的復雜度是O(n*logn),如快速排序\堆排序\歸并排序.在一般情況下和最壞情況下復雜度更是達到O(n**2).

        為了降低復雜度,就有牛人想出了分配收集排序方法,稍后分析它的時間復雜度能到達O(n),

而基數(shù)排序就是一種典型的搜集分配收集排序方法.基數(shù)排序時一種借助于多關(guān)鍵字排序的思想對單關(guān)鍵字排序的方法.其基本思想是通過對排序記錄進行若干趟(有幾個關(guān)鍵字就幾趟)"分配"與"收集"來實現(xiàn)排序.

        如:

       1. 對整數(shù)排序,建立編號0-9(10進制的基數(shù))10個桶,用于裝對應(yīng)位為編號的記錄.先將待排序序列分配按'個位'數(shù)字分配到10各桶中,然后將桶按從小到大的順序串接起來.

        2.將上一步的結(jié)果再按'十位''數(shù)字分配到10各桶中,然后將桶按從小到大的順序串接起來.

        3. 將上一步的結(jié)果再按'百位''數(shù)字分配到10各桶中,然后將桶按從小到大的順序串接起來.

        4.如果還有千位\萬位.重復以上步驟,直到完成最高位的分配與收集,排序結(jié)束.

動圖示例:(轉(zhuǎn)自菜鳥教程:1.10 基數(shù)排序 | 菜鳥教程 (runoob.com))

 

算法實現(xiàn)

1.本實現(xiàn)借助隊列的數(shù)據(jù)結(jié)構(gòu),所以先來定義一個隊列

# 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.處理輸入數(shù)據(jù)

將一個列表作為輸入,將每一個記錄處理為具有相同位數(shù)的字符串(用字符串類型時為了方便處理)

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的方式轉(zhuǎn)化為一樣的長度

3.基數(shù)排序主函數(shù)

def radixSort(seq:list):
    source_data = inDataProcess(seq)  # 輸入處理
    res = []  # 用于保存結(jié)果列表
    big_queue = Queue()  # 用于轉(zhuǎn)化的隊列
    for ele in source_data:
        big_queue.enqueue(ele)
 
    for i in range(len(source_data[0])-1,-1,-1):
        buckets = []  # 用于保存每一趟的10各基數(shù)桶
        for num  in range(10):  # 建立10個基數(shù)桶
            bucket = Queue()
            buckets.append(bucket)
        # 在基數(shù)桶中插入數(shù)據(jù)
        while not big_queue.isEmpty():
            currentEle = big_queue.dequeue()  # 大隊列中出隊一個元素
            index = int(currentEle[i])  # 根據(jù)元素對應(yīng)位上的值添加進對應(yīng)的基數(shù)桶中
            buckets[index].enqueue(currentEle)
 
        # 把基數(shù)桶串聯(lián)起來
        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
    # 將大隊列中的元素保存到結(jié)果列表中
    while not big_queue.isEmpty():
        res.append(big_queue.dequeue().lstrip('0'))  # 利用lstrip('0')去掉前導0
    return res

4.測試及結(jié)果

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))
    ''' 結(jié)果>>>['4', '8', '20', '39', '58', '101', '138', '157', '199', '208', '389', '400', '401', '431', '600', '634', '691',
    '843', '856', '923', '932', '999']'''

算法分析

1)時間復雜度
對于n個記錄(假設(shè)每個記錄含d個關(guān)鍵字,每個關(guān)鍵字的取值范圍為rd個值)進行鏈式基數(shù)排序時,每一趟分配的時間復雜度為O(n),每一趟收集的時間復雜度為O(rd),整個排序需進行d趟分配和收集,所以時間復雜度為O(d(n+rd))。
(2)空間復雜度
所需輔助空間為2rd個隊列指針,另外由于需用鏈表做存儲結(jié)構(gòu),則相對于其他以順序結(jié)構(gòu)存儲記錄的排序方法而言,還增加了n個指針域的空間,所以空間復雜度為O(n+rd)。

算法的特征

(1)是穩(wěn)定排序。
(2)可用于鏈式結(jié)構(gòu),也可用于順序結(jié)構(gòu)。
(3)時間復雜度可以突破基于關(guān)鍵字比較一類方法的下界O(nlog2n),達到O(n)。
(4)基數(shù)排序使用條件有嚴格的要求:需要知道各級關(guān)鍵字的主次關(guān)系和各級關(guān)鍵字的取值范圍。


ref: 

1.嚴蔚敏等數(shù)據(jù)結(jié)構(gòu)C語言版(第二版)>>

2.Bradley N. Miller, David L. Ranum Introduction to Data Structures and Algorithms in Python>>

到此這篇關(guān)于python之基數(shù)排序的實現(xiàn)的文章就介紹到這了,更多相關(guān)python之基數(shù)排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

您可能感興趣的文章:
  • 10個python3常用排序算法詳細說明與實例(快速排序,冒泡排序,桶排序,基數(shù)排序,堆排序,希爾排序,歸并排序,計數(shù)排序)
  • 基于python進行桶排序與基數(shù)排序的總結(jié)
  • Python數(shù)據(jù)結(jié)構(gòu)與算法之常見的分配排序法示例【桶排序與基數(shù)排序】
  • Python實現(xiàn)的基數(shù)排序算法原理與用法實例分析
  • python簡單實現(xiàn)基數(shù)排序算法
  • python計數(shù)排序和基數(shù)排序算法實例
  • python算法學習之基數(shù)排序?qū)嵗?/li>

標簽:雅安 許昌 七臺河 贛州 濰坊 辛集 西安 渭南

巨人網(wǎng)絡(luò)通訊聲明:本文標題《python之基數(shù)排序的實現(xiàn)》,本文關(guān)鍵詞  python,之,基數(shù),排序,的,實現(xiàn),;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《python之基數(shù)排序的實現(xiàn)》相關(guān)的同類信息!
  • 本頁收集關(guān)于python之基數(shù)排序的實現(xiàn)的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章