快捷導(dǎo)航

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

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

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

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

基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（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)代碼如下：

#-*- coding: UTF-8 -*-
import numpy as np
def 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 += 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 "---------------------------------------------------------------"

運(yùn)行結(jié)果：