20191106-基于Python的对字母基数排序
基数排序
概念
基数排序的算法过程是先将待排元素补位,使其长度一致,然后按照序列中的元素的每个位数进行分桶的一种算法。
比如待排序列是数字,则将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序分类
基数排序的方式分为2类:
- LSD(Least significant digital):LSD的排序方式由键值的最右边开始,先比较最低位,也就是个位,进行分桶,分桶过程中分到一个桶中的数据直接追加到桶中即可,无需排序。然后将所有同种的元素按桶的顺序拿出,重新组成序列,然后比较十位,进行分桶…直到比较到最高位,重新组成序列即可完成排序。
- MSD(Most significant digital):由键值的最左边开始,先比较最高位,最高位分到一个桶中的,再按照第二位进行分桶…,知道分到最后一位,然后再从最小的桶中逐层向上,把元素都拿出来,即完成排序。
算法过程
1. 不管待排列表是多少个元素,以及元素的长度为多少,都需要创建27个桶,分别对应其他字符以及a-z的26个英文字母
2. 获取待排元素的的最长的单词作为排序的轮数
3. 从低位到高位依次排序(注意:一定是要从地位到高位才能完成我们的字典序)
具体代码分为2个函数,一个函数是获取字母应该放置到哪个桶中,一个函数根据获取的桶的索引将元素放置入桶中
代码
代码1:根据给定单词,以及给定单词的字母的索引(表示当前按照单词的第几个字母进行放置入桶)返回对应的桶的索引
#根据给定英文字母获取对应的桶的索引 |
代码2:根据代码1返回的桶的索引放置单词,并且放置后按照桶的位置从0-26逐一取出桶中的单词放回序列,然后进行下一轮排序,一直到排序完最后一轮
# 遍历待排列表,进行排序 |
因为python代码的特定,简化算法代码如下:
origin_arr = ["banana","apple","orange","ape","he"] |
arr.sort(key=lambda
x:x[-1-i])表示先比较最后一位,再比较倒数第二位,倒数第三位。。。
原文参考:
小灰公众号,还有一个博客找不到了,如侵权,请联系本人删除
最新文章
- 《高性能javascript》 领悟随笔之-------DOM编程篇
- iptables 思维导图 (zz)
- WebCrawler
- 15 个最佳的 jQuery 表格插件
- 编译为 Release 与 Debug 的区别
- 直接拿来用 九个超实用的PHP代码片段(二)
- 使用Pig预测电信用户的移动路径
- hbase 0.96 单机伪分布式配置文件及遇到的问题 find命令
- (转)Div+CSS布局入门
- Your build host version of Xamarin.IOS (release NO.)is too recent to work with the IOS designer
- centos 配置 php 执行shell的权限
- NSString的几种常用方法—韩俊强博…
- windows下mysql忘记root密码的解决办法
- mysql分区表之三:MySQL分区建索引[转]
- [控件] 心形加载的view
- 获取SQL Server中连接的客户端IP地址[转]
- servlet Filter过滤javascript
- #ifdef 和 #if defined的区别
- jQuery面向对象的写法
- java字符编码(转)
热门文章
- 蚂蚁金服财富技术部,诚招Java研发工程师。校招内推!!!
- python实用技巧之任务切分
- unity手机游戏应用程序调试控制台Lunar Mobile Console - PRO 1.5.5
- 高通平台打开 dynamic debug方法【学习笔记】
- python 与开源Gis 书本知识点测试
- Apache log4j 1.2 - Short introduction to log4j
- Linux_CentOS用户管理 和 用户权限管理 chmod、ACL、 visudo
- flutter 打开应用的闪屏动画
- 【转载】 tf.split函数的用法
- Spring Cloud Eureka 服务发现 4.2