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

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

本代碼介紹了python算法學(xué)習(xí)中的基數(shù)排序?qū)嵗蠹覅⒖际褂冒?/div>

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

復(fù)制代碼 代碼如下:

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

def _counting_sort(A, i):
    """計(jì)數(shù)排序，以i位進(jìn)行排序，以適用于基數(shù)排序。
    Args:
        A (Sequence): 排序數(shù)組
        i (int): 位數(shù)，從0開(kāi)始而不是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ù)排序，從最低位進(jìn)行排序直到最高位：
    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ù)值所對(duì)應(yīng)元素（[0-9]10個(gè)桶）
        for a in A: # 遍歷元素
            S[a / (10 ** i) % 10].append(a) # 存放對(duì)應(yīng)位數(shù)值的元素（元素當(dāng)前位值在哪個(gè)桶就放進(jìn)去）
        A = [a for b in S for a in b] # 以當(dāng)前位數(shù)值排序好的A（依次從各桶里把元素拿出來(lái)）
    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簡(jiǎn)單實(shí)現(xiàn)基數(shù)排序算法
• python計(jì)數(shù)排序和基數(shù)排序算法實(shí)例
• Python實(shí)現(xiàn)的基數(shù)排序算法原理與用法實(shí)例分析
• python算法學(xué)習(xí)之桶排序算法實(shí)例(分塊排序)
• Python實(shí)現(xiàn)桶排序與快速排序算法結(jié)合應(yīng)用示例
• Python實(shí)現(xiàn)的桶排序算法示例
• Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解
• Python排序搜索基本算法之插入排序?qū)嵗治?/a>
• Python排序搜索基本算法之選擇排序?qū)嵗治?/a>
• Python排序搜索基本算法之冒泡排序?qū)嵗治?/a>
• Python排序搜索基本算法之希爾排序?qū)嵗治?/a>
• Python數(shù)據(jù)結(jié)構(gòu)與算法之常見(jiàn)的分配排序法示例【桶排序與基數(shù)排序】

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

相關(guān)文章

• 

  Python 使用os.remove刪除文件夾時(shí)報(bào)錯(cuò)的解決方法

  下面小編就為大家?guī)?lái)一篇Python 使用os.remove刪除文件夾時(shí)報(bào)錯(cuò)的解決方法。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

  2017-01-01
• 

  如何安裝多版本python python2和python3共存以及pip共存

  這篇文章主要為大家詳細(xì)介紹了python多版本的安裝方法，解決python2和python3共存以及pip共存問(wèn)題，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

  2018-09-09
• 

  使用OpenCV對(duì)運(yùn)動(dòng)員的姿勢(shì)進(jìn)行檢測(cè)功能實(shí)現(xiàn)

  2022年奧林匹克運(yùn)動(dòng)會(huì)如期舉行，以不正確的方式進(jìn)行運(yùn)動(dòng)風(fēng)險(xiǎn)在增加，人體姿勢(shì)估計(jì)是計(jì)算機(jī)視覺(jué)領(lǐng)域的重要問(wèn)題，接下來(lái)通過(guò)本文給大家介紹下使用OpenCV對(duì)運(yùn)動(dòng)員的姿勢(shì)進(jìn)行檢測(cè)功能，感興趣的朋友一起看看吧

  2022-02-02
• 

  python爬蟲入門教程--正則表達(dá)式完全指南（五）

  要想做爬蟲，不可避免的要用到正則表達(dá)式，如果是簡(jiǎn)單的字符串處理，類似于split，substring等等就足夠了，可是涉及到比較復(fù)雜的匹配，當(dāng)然是正則的天下，下面這篇文章主要給大家介紹了python爬蟲之正則表達(dá)式的相關(guān)資料，需要的朋友可以參考下。

  2017-05-05
• 

  2023最新pytorch快速安裝指南(超詳細(xì)版)

  這篇文章主要給大家介紹了2023年最新pytorch快速安裝指南的相關(guān)資料,PyTorch是一個(gè)開(kāi)源的深度學(xué)習(xí)框架,提供了各種張量操作并通過(guò)自動(dòng)求導(dǎo)可以自動(dòng)進(jìn)行梯度計(jì)算,方便構(gòu)建各種動(dòng)態(tài)神經(jīng)網(wǎng)絡(luò),需要的朋友可以參考下

  2023-10-10
• 

  Python實(shí)用技巧之利用元組代替字典并為元組元素命名

  這篇文章主要給大家介紹了關(guān)于Python實(shí)用技巧之利用元組代替字典并為元組元素命名的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起看看吧

  2018-07-07
• 

  python使用循環(huán)打印所有三位數(shù)水仙花數(shù)的實(shí)例

  今天小編就為大家分享一篇python使用循環(huán)打印所有三位數(shù)水仙花數(shù)的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

  2018-11-11
• 

  詳解在Python程序中使用Cookie的教程

  這篇文章主要介紹了詳解在Python程序中使用Cookie的教程,Cookie在無(wú)論哪種語(yǔ)言的網(wǎng)絡(luò)編程學(xué)習(xí)當(dāng)中都是重要的知識(shí)點(diǎn),需要的朋友可以參考下

  2015-04-04
• 

  Python3中urlencode和urldecode的用法詳解

  今天小編就為大家分享一篇Python3中urlencode和urldecode的用法詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

  2019-07-07
• 

  python3 模擬登錄v2ex實(shí)例講解

  下面小編就為大家?guī)?lái)一篇python3 模擬登錄v2ex實(shí)例講解。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

  2017-07-07

最新評(píng)論