python中怎么實現基數排序

python中怎么實現基數排序，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

一、桶排序：

排序一個數組[5,3,6,1,2,7,5,10]

值都在1-10之間，建立10個桶：

[0 0 0 0 0 0 0 0 0 0] 桶

[1 2 3 4 5 6 7 8 9 10] 桶代表的值

遍歷數組，第一個數字5，第五個桶加1

[0 0 0 0 1 0 0 0 0 0]

第二個數字3，第三個桶加1

[0 0 1 0 1 0 0 0 0 0]

遍歷后

[1 1 1 0 2 1 1 0 0 1]

輸出

[1 2 3 5 5 6 7 10]

代碼：

def bucket_sort(lst):
 buckets = [0] * ((max(lst) - min(lst))+1)
 for i in range(len(lst)):
  buckets[lst[i]-min(lst)] += 1
 res=[]
 for i in range(len(buckets)):
  if buckets[i] != 0:
   res += [i+min(lst)]*buckets[i]
 return res

二、基數排序：

例如，對如下數據序列進行排序。

192,221,12,23

可以觀察到它的每個數據至多只有3位，因此可以將每個數據拆分成3個關鍵字：百位（高位）、十位、個位（低位）。如果按照習慣思維，會先比較百位，百位大的數據大，百位相同的再比較十位，十位大的數據大；最后再比較個位。基數排序方法對任一子關鍵字排序時必須借助于另一種排序方法，而且這種排序方法必須是穩定的。對于多關鍵字拆分出來的子關鍵字，它們一定位于0-9這個可枚舉的范圍內，這個范圍不大，因此用桶式排序效率非常好。

代碼：

from random import randint
def radix_sort(lis,d):
 for i in xrange(d):#d輪排序
  s = [[] for k in xrange(10)]#因為每一位數字都是0~9，故建立10個桶
  for j in lis:
   s[j/(10**i)%10].append(i)
  li = [a for b in s for a in b]
 return li

對數組中的元素按照從低位到高位排序，對于[192,221,12,23]第一輪按照個位數字相同的放在一組，是s[1] =[221],s[2]=[192,12],s[3]=23,第二輪按照十位數字進行排序，s[1]=[12],s[2]=[221,23],s[9]=[192],第三輪按照百位數字進行排序，s[0]=[12,23],s[1]=[192],s[2]=[221]

看完上述內容，你們掌握python中怎么實現基數排序的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！