Python编程1000例(29):排序算法——基数排序法

发表时间:2021-05-11

本系列文章通过 1000(一篇文章表示 1 个实例) 个实例 ,为读者提供较为详细的练习题目,以便读者举一反三,深度学习。本系列的文章涉及到 Python 知识点包括:Python 语言基础、运算符和表达式、语句和程序结构、列表和元组、字典和集合、字符串、正则表达式、函数、面向对象编程、模块和包、异常处理和程序调试、文件和目录操作、数据库编程、界面编程、网络编程、WEB 编程、进程和线程、网络爬虫、游戏编程等知识点,由易到难,由浅入深,一步步打下坚实的编程基础。

本系列文章涉及的算法包括搜索、回溯、递归、排序、迭代、贪心、分治和动态规划等,涉及的数据结构包括字符串、列表、指针、区间、队列、矩阵、堆栈、链表、哈希表、线段树、二叉树、二叉搜索树和图结构等。

本系列文章是笔者为适应当前教育改革的创新要求,更好地践行语言类课程,满足实践教学与创新能力培养的需要,阅读大量书籍、各大互联网公司的面试算法、LintCode、LeetCode、九章算法和结合笔者近几年项目经验编写的系列文章,精选了 1000 个趣味性、实用性强的应用实例,从不同难度、不同算法、不同类型和不同数据结构等方面,将实际算法进行总结,希望为 Python 编程人员抛砖引玉。由于笔者经验与水平有限,博文中疏漏及不妥之处在所难免,衷心地希望各位读者在评论区多提宝贵意见及具体的修改建议,以便笔者进一步修改和完善。

一、基数排序法

基数排序法和计数排序法一样,都是一种非交换排序。基数排序过程和计数排序过程都需要借助桶来进行。基数排序的主要思想是设置若干个桶,将关键字为 k 的记录放入第 k 个桶,然后按序号将非空的数据连接。关键字 k 就是将每个数据按个位、十位、百位…进行分割而产生的。基数排序不仅仅可以应用在数字之间的排序,还可以应用在字符串排序(按26个字母顺序)等。

接下来用一组数据来详细讲解基数排序法。例如有这样一组数据 410、265、52、530、116、789、110,如下图所示:
在这里插入图片描述
按照递增进行排序,步骤如下:

步骤1 :无论是个位、十位、百位都是由数字 0~9 组成,因此桶号也应该是从 0~9,例如创建桶如图所示:
在这里插入图片描述
步骤2 :将原始数据中的数字先按个位数分类,即数字 410 的个位是 0,数字 256 的个位是 6,数据 52 的个位是 2,按照此规律得知,此数据的个位数分别是 0、5、2、0、6、9、0,将其放在对应的桶中,如下图所示:
在这里插入图片描述
步骤3 :按照桶号顺序,将数据从各个桶中取出来。取出的数据顺序如图所示:
在这里插入图片描述
步骤4 :再将上图中取出来的数据按十位数分类,即 410 的十位是 1,530 的十位是 3,按照此规律得知,此数据的十位数分别是 1、3、1、5、6、1、8,将其放在对应的桶中,如下图所示:
在这里插入图片描述
步骤5 :按照桶号顺序,将数据从各个桶中取出来。取出的数据顺序如图所示:
在这里插入图片描述
步骤6 :再将上图中取出来的数据按百位数分类,即 410 的百位是 4,110 的百位是 1,按照此规律得知,此数据的百位数分别是 4、1、1、5、0、2、7,将其放在对应的桶中,如图所示:
在这里插入图片描述
步骤7 :按照桶号顺序,将数据从各个桶中取出来。取出的数据顺序如图所示:
在这里插入图片描述
从上图中的结果来看,已经将数据排序好,这就是基数排序法的过程。接下来用 Python 代码实现基数排序法。

二、实例:使用基数排序法为列表中的数字进行递增排序

具体代码如下:

def radix_sort(data):  # 基数排序,参数data是待排序数列
    i = 0  # 记录当前正在排拿一位,最低位为1
    max_num = max(data)  # 最大值
    j = len(str(max_num))  # 记录最大值的位数
    while i < j:
        # 初始化桶数组,因为每一位数字都是0~9,故建立10个桶,列表中包含十个列表元素
        bucket_list = [[] for x in range(10)]
        for x in data:  # 找数据s
            bucket_list[int(x / (10 ** i)) % 10].append(x)  # 找到位置放入桶数组
        print(bucket_list)  # 打印每次的桶情况
        data.clear()  # 将原data置空
        for x in bucket_list:  # 放回原data序列
            for y in x:  # 遍历排序后的结果
                data.append(y)  # 放数据
        i += 1  # 执行一次,向后继续拿数据执行循环


data = [410, 265, 52, 530, 116, 789, 110]  # 待排序列表
radix_sort(data)  # 调用基数排序函数
print(data)  # 输出排序结果

运行结果如下图所示:
在这里插入图片描述
从结果上看,每行有十个列表,表示 0~9 号桶,每个列表包含的数据就是上述步骤放入桶中的数据,完全符合上述讲解的步骤。

感谢您阅读本篇博文,希望本文能成为您编程路上的领航者。祝您阅读愉快!


在这里插入图片描述

好书不厌读百回,熟读课思子自知。而我想要成为全场最靓的仔,就必须坚持通过学习来获取更多知识,用知识改变命运,用博客见证成长,用行动证明我在努力。
如果我的博客对你有帮助、如果你喜欢我的博客内容,请 点赞 评论 收藏 一键三连哦!听说点赞的人运气不会太差,每一天都会元气满满呦!如果实在要白嫖的话,那祝你开心每一天,欢迎常来我博客看看。
编码不易,大家的支持就是我坚持下去的动力。点赞后不要忘了 关注 我哦!

文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号-4
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free