python算法學習之基數(shù)排序?qū)嵗?/h1>

 更新時間：2013年12月18日 10:08:05   作者：  

本代碼介紹了python算法學習中的基數(shù)排序?qū)嵗?，大家參考使用?/div>

基數(shù)排序法又稱桶子法（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些"桶"中，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的比較性排序法。

復制代碼 代碼如下:

# -*- coding: utf-8 -*-

def _counting_sort(A, i):
    """計數(shù)排序，以i位進行排序，以適用于基數(shù)排序。
    Args:
        A (Sequence): 排序數(shù)組
        i (int): 位數(shù)，從0開始而不是1
    """
    C = [0] * 10 # 任意位值范圍為[0,9]
    A = [(a / (10 ** i) % 10, a) for a in A] # 元素i位值及其自身的元組的數(shù)組
    for k, a in A:
        C[k] = C[k] + 1
    for i in xrange(1, 10):
        C[i] = C[i] + C[i-1]
    B = [0] * len(A) # 結(jié)果數(shù)組
    for k, a in A[::-1]:
        B[C[k]-1] = a
        C[k] = C[k] - 1
    return B

def radix_sort(A, d):
    """基數(shù)排序，從最低位進行排序直到最高位：
    RADIX-SORT(A, d)
    1  for i ← 1 to d
    2    do use a stable sort to sort array A on digit i

    Args:
        A (Sequence): 排序數(shù)組
        d (int): 最大數(shù)位數(shù)
    """
    for i in xrange(d): # 遍歷位數(shù)，從低到高
        A = _counting_sort(A, i)
    return A

def rsort(A, d):
    """基數(shù)排序（桶排序版本）"""
    for i in xrange(d): # 遍歷位數(shù)，從低到高
        S = [[] for _ in xrange(10)] # 存放[0,9]位數(shù)值所對應元素（[0-9]10個桶）
        for a in A: # 遍歷元素
            S[a / (10 ** i) % 10].append(a) # 存放對應位數(shù)值的元素（元素當前位值在哪個桶就放進去）
        A = [a for b in S for a in b] # 以當前位數(shù)值排序好的A（依次從各桶里把元素拿出來）
    return A

if __name__ == '__main__':
    import random, timeit

    items = range(10000)
    random.shuffle(items)

    def test_sorted():
        print(items)
        sorted_items = sorted(items)
        print(sorted_items)

    def test_radix_sort():
        print(items)
        sorted_items = radix_sort(items, 4) # [0,9999]，4位數(shù)
        print(sorted_items)

    test_methods = [test_sorted, test_radix_sort]
    for test in test_methods:
        name = test.__name__ # test.func_name
        t = timeit.Timer(name + '()', 'from __main__ import ' + name)
        print(name + ' takes time : %f' % t.timeit(1))

您可能感興趣的文章:

• python簡單實現(xiàn)基數(shù)排序算法
• python計數(shù)排序和基數(shù)排序算法實例
• Python實現(xiàn)的基數(shù)排序算法原理與用法實例分析
• python算法學習之桶排序算法實例(分塊排序)
• Python實現(xiàn)桶排序與快速排序算法結(jié)合應用示例
• Python實現(xiàn)的桶排序算法示例
• Python實現(xiàn)的數(shù)據(jù)結(jié)構與算法之快速排序詳解
• Python排序搜索基本算法之插入排序?qū)嵗治?/a>
• Python排序搜索基本算法之選擇排序?qū)嵗治?/a>
• Python排序搜索基本算法之冒泡排序?qū)嵗治?/a>
• Python排序搜索基本算法之希爾排序?qū)嵗治?/a>
• Python數(shù)據(jù)結(jié)構與算法之常見的分配排序法示例【桶排序與基數(shù)排序】

• python算法
• 基數(shù)排序

相關文章

• 

  python如何實現(xiàn)wifi自動連接,解決電腦wifi經(jīng)常斷開問題

  這篇文章主要介紹了python實現(xiàn)wifi自動連接,解決電腦wifi經(jīng)常斷開的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

  2023-06-06
• 

  Gauss-Seidel迭代算法的Python實現(xiàn)詳解

  這篇文章主要介紹了Gauss-Seidel迭代算法的Python實現(xiàn)詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

  2019-06-06
• 

  Python變量及數(shù)據(jù)類型用法原理匯總

  這篇文章主要介紹了Python變量及數(shù)據(jù)類型用法原理匯總,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

  2020-08-08
• 

  pandas統(tǒng)計重復值次數(shù)的方法實現(xiàn)

  這篇文章主要介紹了pandas統(tǒng)計重復值次數(shù)的方法實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

  2021-02-02
• 

  python隊列通信:rabbitMQ的使用(實例講解)

  下面小編就為大家分享一篇python隊列通信:rabbitMQ的使用(實例講解)，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

  2017-12-12
• 

  解決PIP安裝第三方庫報錯SSL: CERTIFICATE_VERIFY_FAILED問題

  這篇文章主要介紹了解決PIP安裝第三方庫報錯SSL: CERTIFICATE_VERIFY_FAILED問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

  2024-01-01
• 

  Python itertools.product方法代碼實例

  這篇文章主要介紹了Python itertools.product方法代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

  2020-03-03
• 

  用Python制作檢測Linux運行信息的工具的教程

  這篇文章主要介紹了用Python制作檢測Linux運行信息的工具的教程,主要是用CPython讀取運行系統(tǒng)的硬件參數(shù)、網(wǎng)絡傳輸流量統(tǒng)計等，需要的朋友可以參考下

  2015-04-04
• 

  利用ctypes獲取numpy數(shù)組的指針方法

  今天小編就為大家分享一篇利用ctypes獲取numpy數(shù)組的指針方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

  2019-02-02
• 

  python networkx 根據(jù)圖的權重畫圖實現(xiàn)

  這篇文章主要介紹了python networkx 根據(jù)圖的權重畫圖實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

  2019-07-07

最新評論