快捷導(dǎo)航

Python實現(xiàn)的基數(shù)排序算法原理與用法實例分析

更新時間：2017年11月23日 09:02:18 作者：Alex Yu

這篇文章主要介紹了Python實現(xiàn)的基數(shù)排序算法,簡單說明了基數(shù)排序的原理并結(jié)合實例形式分析了Python實現(xiàn)與使用基數(shù)排序的具體操作技巧,需要的朋友可以參考下

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

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

實現(xiàn)代碼如下：

#-*- coding: UTF-8 -*-
import numpy as np
def RadixSort(a):
  i = 0                       #初始為個位排序
  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, [])  #將每個桶置空
    for x in a:                #對每一位進行排序
      radix =(x / (10**i)) % 10  #得到每位的基數(shù)
      bucket[radix].append(x) #將對應(yīng)的數(shù)組元素加入到相應(yīng)位基數(shù)的桶中
    j = 0
    for k in xrange(0, 10):
      if len(bucket[k]) != 0:    #若桶不為空
        for y in bucket[k]:     #將該桶中每個元素
          a[j] = y            #放回到數(shù)組中
          j += 1
    i += 1
if __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 "---------------------------------------------------------------"

運行結(jié)果：