本文實(shí)例講述了Python實(shí)現(xiàn)的基數(shù)排序算法。分享給大家供大家參考，具體如下：
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱(chēng)“桶子法”（bucket sort）或bin sort，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
實(shí)現(xiàn)代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#-*- coding: UTF-8 -*-import numpy as npdef RadixSort(a): i = 0 #初始為個(gè)位排序 n = 1 #最小的位數(shù)置為1（包含0） max = np.max(a) #得到帶排序數(shù)組中最大數(shù) while max/(10**n) > 0: #得到最大數(shù)是幾位數(shù) n += 1 while i < n: bucket = {} #用字典構(gòu)建桶 for x in xrange(0,10): bucket.setdefault(x, []) #將每個(gè)桶置空 for x in a: #對(duì)每一位進(jìn)行排序 radix =(x / (10**i)) % 10 #得到每位的基數(shù) bucket[radix].append(x) #將對(duì)應(yīng)的數(shù)組元素加入到相應(yīng)位基數(shù)的桶中 j = 0 for k in xrange(0, 10): if len(bucket[k]) != 0: #若桶不為空 for y in bucket[k]: #將該桶中每個(gè)元素 a[j] = y #放回到數(shù)組中 j += 1 i += 1if __name__ == '__main__': a = np.random.randint(0, 1000, size = 10) print "Before sorting..." print "---------------------------------------------------------------" print a print "---------------------------------------------------------------" RadixSort(a) print "After sorting..." print "---------------------------------------------------------------" print a print "---------------------------------------------------------------" |
運(yùn)行結(jié)果：
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
原文鏈接：http://www.cnblogs.com/biaoyu/p/4831648.html
