文档章节

python排序 基数排序

o
 osc_ogi0qclx
发布于 2019/08/23 20:20
字数 837
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

算法思想

基数排序通过按位比较(一般从最低位开始)将元素按照最低位的数放到10个桶中,当所有的元素都这样被处理一次后,在按从0到9的顺序将每个桶的元素再取出来(不关注其他位的,只关注当前位的)这样就完成了所有元素最低位的有序性,然后不断的重复上面的步骤,知道所有元素的最高位都经过处理了。

 

算法步骤

初始化桶,共有10个,分别存放当前位位0-9的元素

从元素的最后一位开始,按照最后一位的数字将其放到相应的同元素中。对列表中的每个元素都进行上面的操作后,从0号桶开始,将元素从桶中取出来,这样就完成了一个位数的排序

重复上一过程,如果发现元素最高位已经被处理过,就把他添加到最终的结果中

 

算法实现

算法的主要问题在于对当前位的获取中

对于正数

(element//divisor)%10#结果是当前位上的数#divisor代表当前位,个位是1,十位是10,百位是100#//是向下取整的意思

  如过element//divisor结果为0 就代表实际结果小于1了,即当前位已经是0了

 

对于负数

collection[j]//i==-1#代表是负数

  取得当前位

(10-math.ceil(element/divisor)%10)%10#math.ceil()是向上取整
#最后一个%10是防止前面结果=10的情况出现

 

算法实现

def radix_sort3(collection):
    ''' 考虑是否可以将负数通过abs转为正数来判断
        外层循环控制进位,即先排最低位的,然后排倒数第二位的..一直处理到每个元素的最高位 ,最高为处理后,放到最终结果集中
        内层循环控制数组元素的遍历
        对每个数组元素,首先分大于0和小于0的两种情况,因为涉及到正数和负数的寻找最低位数字的算法逻辑大小不一样
        对正数来说,分为当前进位后还有元素此时放到临时变量中,当前进位就是最后一位此时就放到最终的结果集中,相应的判断逻辑解释见版本0
        负数也和上面差不多
        在内层for结束以后,还需要将临时变量中的元素给取出来'''
    result_negative=[]
    result_positive=[]
    divisor=[pow(10,i) for i in range(10)]
    for i in divisor:
        bucket=[[] for j in range(10)]
        if len(collection)==0:
            break
        for j in range(len(collection)):
            if collection[j]//i>0:
                bucket[(collection[j]//i)%10].append(collection[j])
                continue
            elif collection[j]//i==0:
                result_positive.append(collection[j])
                continue
            #负数的
            # elif collection[j]//i<-1:
            #     bucket[(10-math.ceil(collection[j]/i)%10)%10].append(collection[j])
            #     continue
            # elif collection[j]//i==-1:#会出现bug,-100/100=-1,然后就被放到了最终结果中,但其实不应该被这样的
            #     if math.ceil(collection[j]/i)==-1:
            #         bucket[(10-math.ceil(collection[j]/i)%10)%10].append(collection[j])
            #         continue
            #     result_negative.insert(0,collection[j])
            #     continue
        collection=[]
        for k in bucket:
            if k:
                collection.extend(k)
    return result_negative+result_positive

 

效率分析

时间复杂度:进行k次关于数位的循环,每次循环里还有一个循环,要对N个元素进行放桶,一共循环kN

 

对比

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
python实现线性排序-基数排序

  基数排序算法是一种是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。 由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所...

osc_5s0xzojq
2018/01/11
1
0
python数组排序的方法

排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录...

osc_9vxdigiw
2019/12/24
1
0
Python - 八大排序算法

1、序言 本文使用Python实现了一些常用的排序方法。文章结构如下: 1.直接插入排序 2.希尔排序 3.冒泡排序 4.快速排序 5.简单选择排序 6.堆排序 7.归并排序 8.基数排序 上述所有的排序均写在...

骑着螞蟻流浪
01/06
0
0
【代码】Pythonの代码片段

实用方法 Pythonの清理文件及文件夹 Pythonの获取Gravatar头像地址 Pythonの获取beautifulphoto随机某图片 2) 排序算法 2.1) 比较排序 Pythonの插入排序 Pythonの合并排序 Pythonの冒泡排序 ...

加壹
2013/05/19
845
1
python算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:...

osc_fzp57c02
2019/06/17
2
0

没有更多内容

加载失败,请刷新页面

加载更多

科技人文丨玻璃心:承受阈值与表达

大家好,我是SKODE。 有趣的灵魂,聊科技人文。 本系列博客地址:传送门 本文转载自B站:安慰记传送门 玻璃心是网络用语,意思是: 对负面事件的接受度很低 还有对别人可能给出的负面评价非常...

osc_u9mt0sus
54分钟前
20
0
迅睿CMS 游客不允许上传附件

游客不允许上传附件 迅睿CMS系统:https://www.xunruicms.com/ 本文档原文地址:https://www.xunruicms.com/doc/752.html...

迅睿CMS-PHP开源CMS程序
55分钟前
12
0
代理,注解,接口和实现类的小测验

* retention : 保留* policy : 策略 ps : 简单测试了一下手写代理,jdk动态代理,和cglib动态代理,根据其不同的结果分析其原理 一:测试目的 主要想看一下不同的代理模式对于目标类中方法上注...

岁一
55分钟前
12
0
V-Ray 5 For 3ds Max 正式发布:超越渲染 - 知乎

15个新功能,V-Ray5助你时间更节省,渲染更出色! 作者:ChaosGroup VRay 5 For 3ds Max 已正式发布! 2分钟视频,抢先预览新功能↓ 知乎视频 www.zhihu.com V-Ray 5 for 3ds Max 新增功能 ...

osc_o9u1um45
56分钟前
0
0
毕业的笑容和悲伤永远是校园的回忆

校园的风轻轻的拂过我的脸庞,风儿显得更加凉爽, 开满火红的凤凰树,染遍了校园的每个角落, 晚上那枝头蝉儿的竞相鸣奏,唱满了令人不舍的毕业歌, 它们彷彿告诉了我们要毕业了。 毕业典礼那...

瑾123
56分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部