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

 更新时间:2017年12月15日 11:16:53   作者:hanahimi   我要评论
这篇文章主要介绍了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.sxglgf.com/aideddesign/paixu_ys

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

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

相关文章

  • Python 利用pydub库操作音频文件的方法

    Python 利用pydub库操作音频文件的方法

    今天小编就为大家分享一篇Python 利用pydub库操作音频文件的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-01-01
  • 在Python中使用HTMLParser解析HTML的教程

    在Python中使用HTMLParser解析HTML的教程

    这篇文章主要介绍了在Python中使用HTMLParser解析HTML的教程,尤其是在用Python制作爬虫程序的时候经常可以用到,需要的朋友可以参考下
    2015-04-04
  • Python编程产生非均匀随机数的几种方法代码分享

    Python编程产生非均匀随机数的几种方法代码分享

    这篇文章主要介绍了Python编程产生非均匀随机数的几种方法代码分享,具有一定借鉴价值,需要的朋友可以参考下。
    2017-12-12
  • 在Python中定义一个常量的方法

    在Python中定义一个常量的方法

    今天小编就为大家分享一篇在Python中定义一个常量的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-11-11
  • Python操作Access金沙国际官网基本步骤分析

    Python操作Access金沙国际官网基本步骤分析

    这篇文章主要介绍了Python操作Access金沙国际官网基本步骤,结合实例形式详细分析了Python针对access操作的具体步骤与相关注意事项,需要的朋友可以参考下
    2016-09-09
  • Python快速转换numpy数组中Nan和Inf的方法实例说明

    Python快速转换numpy数组中Nan和Inf的方法实例说明

    今天小编就为大家分享一篇关于Python快速转换numpy数组中Nan和Inf的方法实例说明,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
    2019-02-02
  • 详解Python中dict与set的使用

    详解Python中dict与set的使用

    这篇文章主要介绍了详解Python中dict与set的使用,是Python入门学习中的基础知识,需要的朋友可以参考下
    2015-08-08
  • Python数据分析之如何利用pandas查询数据示例代码

    Python数据分析之如何利用pandas查询数据示例代码

    查询和分析数据是pandas的重要功能,也是我们学习pandas的基础,下面这篇文章主要给大家介绍了关于Python数据分析之如何利用pandas查询数据的相关资料,文中通过示例代码介绍的非常详细,需要的朋友可以参考借鉴,下面来一起看看吧。
    2017-09-09
  • python实现ID3决策树算法

    python实现ID3决策树算法

    这篇文章主要为大家详细介绍了python实现ID3决策树算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2017-12-12
  • 利用python3随机生成中文字符的实现方法

    利用python3随机生成中文字符的实现方法

    最近在学习python3,发现网上关于ptyhon3随机生成中文的资料非常少,所以决定将自己实现的方法分享下,下面这篇文章主要给大家介绍了关于利用python3随机生成中文字符的实现方法,需要的朋友可以参考借鉴,下面来一起看看吧。
    2017-11-11

最新评论