python算法學(xué)習(xí)之基數(shù)排序?qū)嵗?/h1>
更新時間：2013年12月18日 10:08:05 作者：
本代碼介紹了python算法學(xué)習(xí)中的基數(shù)排序?qū)嵗?，大家參考使用?/div>
基數(shù)排序法又稱桶子法（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些"桶"中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的比較性排序法。
復(fù)制代碼 代碼如下:
# -*- coding: utf-8 -*-
def _counting_sort(A, i):
"""計數(shù)排序，以i位進(jìn)行排序，以適用于基數(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ù)排序，從最低位進(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ù)值所對應(yīng)元素（[0-9]10個桶）
for a in A: # 遍歷元素
S[a / (10 ** i) % 10].append(a) # 存放對應(yīng)位數(shù)值的元素（元素當(dāng)前位值在哪個桶就放進(jìn)去）
A = [a for b in S for a in b] # 以當(dāng)前位數(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算法學(xué)習(xí)之桶排序算法實例(分塊排序)
- Python實現(xiàn)桶排序與快速排序算法結(jié)合應(yīng)用示例
- Python實現(xiàn)的桶排序算法示例
- Python實現(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)與算法之常見的分配排序法示例【桶排序與基數(shù)排序】
相關(guān)文章
-
Python 使用os.remove刪除文件夾時報錯的解決方法
下面小編就為大家?guī)硪黄狿ython 使用os.remove刪除文件夾時報錯的解決方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧 2017-01-01
-
如何安裝多版本python python2和python3共存以及pip共存
這篇文章主要為大家詳細(xì)介紹了python多版本的安裝方法，解決python2和python3共存以及pip共存問題，具有一定的參考價值，感興趣的小伙伴們可以參考一下 2018-09-09
-
使用OpenCV對運(yùn)動員的姿勢進(jìn)行檢測功能實現(xiàn)
2022年奧林匹克運(yùn)動會如期舉行，以不正確的方式進(jìn)行運(yùn)動風(fēng)險在增加，人體姿勢估計是計算機(jī)視覺領(lǐng)域的重要問題，接下來通過本文給大家介紹下使用OpenCV對運(yùn)動員的姿勢進(jìn)行檢測功能，感興趣的朋友一起看看吧 2022-02-02
-
python爬蟲入門教程--正則表達(dá)式完全指南（五）
要想做爬蟲，不可避免的要用到正則表達(dá)式，如果是簡單的字符串處理，類似于split，substring等等就足夠了，可是涉及到比較復(fù)雜的匹配，當(dāng)然是正則的天下，下面這篇文章主要給大家介紹了python爬蟲之正則表達(dá)式的相關(guān)資料，需要的朋友可以參考下。 2017-05-05
-
這篇文章主要給大家介紹了2023年最新pytorch快速安裝指南的相關(guān)資料,PyTorch是一個開源的深度學(xué)習(xí)框架,提供了各種張量操作并通過自動求導(dǎo)可以自動進(jìn)行梯度計算,方便構(gòu)建各種動態(tài)神經(jīng)網(wǎng)絡(luò),需要的朋友可以參考下 2023-10-10
-
這篇文章主要給大家介紹了關(guān)于Python實用技巧之利用元組代替字典并為元組元素命名的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧 2018-07-07
-
python使用循環(huán)打印所有三位數(shù)水仙花數(shù)的實例
今天小編就為大家分享一篇python使用循環(huán)打印所有三位數(shù)水仙花數(shù)的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧 2018-11-11
-
這篇文章主要介紹了詳解在Python程序中使用Cookie的教程,Cookie在無論哪種語言的網(wǎng)絡(luò)編程學(xué)習(xí)當(dāng)中都是重要的知識點(diǎn),需要的朋友可以參考下 2015-04-04
-
Python3中urlencode和urldecode的用法詳解
今天小編就為大家分享一篇Python3中urlencode和urldecode的用法詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧 2019-07-07
-
下面小編就為大家?guī)硪黄猵ython3 模擬登錄v2ex實例講解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧 2017-07-07
最新評論
基數(shù)排序法又稱桶子法（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些"桶"中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的比較性排序法。
# -*- coding: utf-8 -*-
def _counting_sort(A, i):
"""計數(shù)排序，以i位進(jìn)行排序，以適用于基數(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ù)排序，從最低位進(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ù)值所對應(yīng)元素（[0-9]10個桶）
for a in A: # 遍歷元素
S[a / (10 ** i) % 10].append(a) # 存放對應(yīng)位數(shù)值的元素（元素當(dāng)前位值在哪個桶就放進(jìn)去）
A = [a for b in S for a in b] # 以當(dāng)前位數(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算法學(xué)習(xí)之桶排序算法實例(分塊排序)
- Python實現(xiàn)桶排序與快速排序算法結(jié)合應(yīng)用示例
- Python實現(xiàn)的桶排序算法示例
- Python實現(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)與算法之常見的分配排序法示例【桶排序與基數(shù)排序】
相關(guān)文章
-
Python 使用os.remove刪除文件夾時報錯的解決方法
下面小編就為大家?guī)硪黄狿ython 使用os.remove刪除文件夾時報錯的解決方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01 -
如何安裝多版本python python2和python3共存以及pip共存
這篇文章主要為大家詳細(xì)介紹了python多版本的安裝方法，解決python2和python3共存以及pip共存問題，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-09-09 -
使用OpenCV對運(yùn)動員的姿勢進(jìn)行檢測功能實現(xiàn)
2022年奧林匹克運(yùn)動會如期舉行，以不正確的方式進(jìn)行運(yùn)動風(fēng)險在增加，人體姿勢估計是計算機(jī)視覺領(lǐng)域的重要問題，接下來通過本文給大家介紹下使用OpenCV對運(yùn)動員的姿勢進(jìn)行檢測功能，感興趣的朋友一起看看吧2022-02-02 -
python爬蟲入門教程--正則表達(dá)式完全指南（五）
要想做爬蟲，不可避免的要用到正則表達(dá)式，如果是簡單的字符串處理，類似于split，substring等等就足夠了，可是涉及到比較復(fù)雜的匹配，當(dāng)然是正則的天下，下面這篇文章主要給大家介紹了python爬蟲之正則表達(dá)式的相關(guān)資料，需要的朋友可以參考下。2017-05-05 - 這篇文章主要給大家介紹了2023年最新pytorch快速安裝指南的相關(guān)資料,PyTorch是一個開源的深度學(xué)習(xí)框架,提供了各種張量操作并通過自動求導(dǎo)可以自動進(jìn)行梯度計算,方便構(gòu)建各種動態(tài)神經(jīng)網(wǎng)絡(luò),需要的朋友可以參考下2023-10-10
- 這篇文章主要給大家介紹了關(guān)于Python實用技巧之利用元組代替字典并為元組元素命名的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧2018-07-07
-
python使用循環(huán)打印所有三位數(shù)水仙花數(shù)的實例
今天小編就為大家分享一篇python使用循環(huán)打印所有三位數(shù)水仙花數(shù)的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-11-11 - 這篇文章主要介紹了詳解在Python程序中使用Cookie的教程,Cookie在無論哪種語言的網(wǎng)絡(luò)編程學(xué)習(xí)當(dāng)中都是重要的知識點(diǎn),需要的朋友可以參考下2015-04-04
-
Python3中urlencode和urldecode的用法詳解
今天小編就為大家分享一篇Python3中urlencode和urldecode的用法詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07 - 下面小編就為大家?guī)硪黄猵ython3 模擬登錄v2ex實例講解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-07-07