Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

本文详细介绍Python数据结构与算法中常见的分配排序方法，旨在为读者提供实用的参考与学习材料。

箱排序（桶排序）

箱排序依据关键字的取值范围（1至m）预先建立m个箱子。该方法要求关键字类型必须是有限的，否则可能产生无限个箱子，导致实用价值降低。因此，箱排序通常仅作为基数排序过程中的中间步骤使用。

桶排序是箱排序的实用化改进版本。它将数据集的范围（例如[0,1)）划分为n个大小相等的子区间，每个子区间视为一个桶。随后，将n条记录分配到各个桶中。由于关键字序列在[0,1)上均匀分布，通常不会有大量记录落入同一个桶中，从而提高了排序效率。

下文介绍的桶排序方法利用字典（dict）实现，因此对于整数类型数据，无需预先分配多余的空间，更加灵活高效。

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)     # 按分配结果拼合

以下内容摘录自《数据结构与算法——理论与实践》。

基数排序可扩展至多关键字排序场景，例如对扑克牌按花色和点数进行排序。一般地，假设线性表包含n个待排序元素，每个元素包含d个关键字{k1, k2, ..., kd}。若线性表对关键字有序，则对于表中任意两个元素r[i]和r[j]（1<=i<=j<=n），均满足以下有序关系：{k1i, k2i, ..., kdi} < {k1j, k2j, ..., kdj}。其中，k1被称为最主位关键字，kd被称为最次位关键字。基数排序主要分两种策略：最高位优先（MSD，most significant digit first）与最低位优先（LSD，least significant digit first）。

MSD策略：首先按k1进行排序分组；若同一组内元素的关键字k1相等，则再对各组按k2排序并分成子组，依此类推，直到对最次位kd对各子组排序完成后，再将各组链接起来。

LSD策略：与MSD相反，LSD先按kd排序，再按kd-1排序，依次类推，直至完成所有关键字的排序。

此外，推荐一款关于排序过程的演示工具供读者参考。

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具： http://tools.jb51.net/aideddesign/paixu_ys

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》。

希望本文所述内容能对大家的Python程序设计有所帮助。