Python實現的基數排序算法原理與用法實例分析

2020-01-04 16:17:08

字體：大中小

來源：轉載

供稿：網友

本文實例講述了Python實現的基數排序算法。分享給大家供大家參考，具體如下：

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

實現代碼如下：

#-*- coding: UTF-8 -*-import numpy as npdef RadixSort(a):  i = 0                       #初始為個位排序  n = 1                      #最小的位數置為1（包含0）  max = np.max(a)            #得到帶排序數組中最大數  while max/(10**n) > 0:       #得到最大數是幾位數    n += 1  while i < n:    bucket = {}               #用字典構建桶    for x in xrange(0,10):      bucket.setdefault(x, [])  #將每個桶置空    for x in a:                #對每一位進行排序      radix =(x / (10**i)) % 10  #得到每位的基數      bucket[radix].append(x) #將對應的數組元素加入到相應位基數的桶中    j = 0    for k in xrange(0, 10):      if len(bucket[k]) != 0:    #若桶不為空        for y in bucket[k]:     #將該桶中每個元素          a[j] = y            #放回到數組中          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 "---------------------------------------------------------------"

運行結果：

Python,基數排序,算法