Python資料結構與演算法常見的分配排序法範例【桶排序與基數排序】_python

這篇文章主要介紹了Python資料結構與演算法之常見的分配排序法,結合實例形式分析了桶排序與基數排序的相關原理及實現技巧,需要學習Python的朋友可以參考下本文，本文實例講述了Python資料結構與演算法之常見的分配排序法。分享給大家供大家參考，具體如下：

箱排序（桶排序）

箱排序是根據關鍵字的取值範圍1~m，預先建立m個箱子，箱排序要求關鍵字類型為有限類型，可能會有無限個箱子，實用價值不大，一般用於基數排序的中間過程。

桶排序是箱排序的實用化變種，其對資料集的範圍，如[0,1) 進行劃分為n個大小相同的子區間，每個子區間為一個桶，然後將n非記錄分配到各桶中。因為關鍵字序列是均勻分佈在[0,1)的，所以一般不會有許多記錄落入同一個桶中。

以下的桶排序方法採用字典實現，所以對於整數類型，並不需要建立多餘空間

#

def BuckSort(A):
 bucks = dict()  # 桶
 for i in A:
  bucks.setdefault(i,[]) # 每个桶默认为空列表
  bucks[i].append(i)  # 往对应的桶中添加元素
 A_sort = []
 for i in range(min(A), max(A)+1):
  if i in bucks:     # 检查是否存在对应数字的桶
   A_sort.extend(bucks[i])  # 合并桶中数据
 return A_sort

# #基數排序

# 基数排序
# 输入：待排序数组s, keysize关键字位数, 亦即装箱次数, radix基数
def RadixSort(s, keysize=4, radix=10):
 # 按关键字的第k分量进行分配 k = 4,3,2,1
 def distribute(s,k):
  box = {r:[] for r in range(radix)}  # 分配用的空箱子
  for item in s:   # 依次扫描s[]，将其装箱
   t = item
   t /= 10**(k-1)
   t %= 10    # 去关键字第k位
   box[t].append(item)
  return box
 # 按分配结果重新排列数据
 def collect(s,box):
  a = 0
  for i in range(radix):
   s[a:a + len(box[i])] = box[i][:] # 将箱子中元素的合并，覆盖到原来的数组中
   a += len(box[i])     # 增加偏移值
 # 核心算法
 for k in range(1,keysize+1):
  box = distribute(s,k)   # 按基数分配
  collect(s,box)     # 按分配结果拼合

#以下摘自：《資料結構與演算法－理論與實踐》

基數排序可以拓展為按多關鍵字排序，例如對撲克牌按花色、按點數排序。

一般地，設線性表有那個待排序元素，每個元素包含d個關鍵字{k1,k2,...,kd}，則該線性表對關鍵字有序指，對於線性表中任兩個元素r[i]和r[j]，1<=i<=j<=n，都滿足下列有序關係：
　　　　{k1i,k2i,...,kdi} < {k1j ,k2j,...,kdj}
其中k1稱為最主位關鍵字，kd稱為最次要關鍵字
其排序方法分為兩種：最高位優先MSD（most significant digit frist）與最低位元優先LSD（least significant digit first）

MSD： 先按k1排序分組，同一組的個元素，若關鍵字k1相等，再對各組按k2排序分成子組，依次類推，直到最次位kd對各子組排序後，再將各組連結起來。

LSD： 與MSD相反，先按kd排序，再對kd-1排序，依次類推。

PS：這裡再為大家推薦一款關於排序的示範工具供大家參考：

##線上動畫示範插入/選擇/冒泡/歸併/希爾/快速排序演算法過程工具：
#http://tools.jb51.net/aideddesign/paixu_ys#以上就是本文所有的內容了，希望可以帶給大家幫助！ ！

相關推薦：

#Python實作字串比對演算法實例程式碼

#Python爬蟲入門心得分享

python中關於logging函式庫的使用總結

以上是Python資料結構與演算法常見的分配排序法範例【桶排序與基數排序】_python的詳細內容。更多資訊請關注PHP中文網其他相關文章！