python计数排序和基数排序算法实例
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
一、计数排序
计数排序(Counting sort)是一种稳定的排序算法
算法的步骤如下：
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K)，空间复杂度为O(N+K)。当K不是很大时，这是一个很有效的线性排序算法。
以下是测试代码：
import random
def jishu(data, max):
"""
基数排序:当输入的元素是 n 个 0 到 k 之间的整数时(k不能太大,即max不能太大)
@param data: 需要排序的数组
@param max: 最大的数
"""
result = [None for i in xrange(len(data))] # 最后的结果
c = [0 for i in range(max+1)]
# 用数组c统计每个值=d的元素个数
for d in data:
c[d] = c[d] + 1
# c[i]表示data中值<=i 的元素个数
for i in range(1, max+1):
c[i] = c[i] + c[i-1]
# 在将C中的元素倒着打印出来就是排序好的
for j in xrange(len(data)-1, -1, -1):
result[c[data[j]]-1] = data[j]
c[data[j]] = c[data[j]] – 1
return result
if __name__ == '__main__':
#制造1000个0到100的数字
print jishu([random.randint(0, 100) for i in range(1000)], 100)
二、基数排序
基数排序排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
以下是一个测试用例：
import random
def jichu(data, length):
"""
基数排 lsd
@param data: 需要排列的组合
@param length: 最大的数据是几位
"""
for l in xrange(length):
s = [[] for i in xrange(10)]
for d in data:
s[d/(10**l) % 10].append(d)
data = [d for s_list in s for d in s_list]
return data
if __name__ == '__main__':
list = [random.randint(1, 99999999) for i in xrange(99)] # 制造99个数据
print jichu(list, 8)
相关文章
这篇文章主要介绍了Python的numpy库下的几个小函数的用法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧2019-07-07
这篇文章主要介绍了Python模块之间的相互引用问题,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下2021-02-02
探索Python?Furl高性能URL构建解析和操作功能实例
本文将提供关于Python?Furl的全面指南,包括安装和配置、基本概念、URL解析、URL构建、查询参数操作、片段处理、实际应用场景以及丰富的示例代码2024-01-01
这篇文章主要介绍了python模仿网页版微信发送消息功能，具有一定的参考价值，感兴趣的小伙伴们可以参考一下2018-02-02
这篇文章主要分享一个python网页请求模块urllib2模块的简单封装代码，有需要的朋友参考下2014-02-02
在Django项目中会碰到一些需求就是查询某个表中的一些字段从某日到某日的数据,你可以像在SQL中那样使用SELECT语句来查找指定字段,本文就来介绍两种方法,感兴趣的可以了解一下2023-10-10
runtestprotocol 是 pytest 执行测试流程中的一个核心函数,它主要负责调用测试函数的“setup”、“call”和“teardown”钩子函数,并生成对应的测试报告,本文将深入探究pytest中runtestprotocol方法的实现,需要的朋友可以参考下2023-10-10
今天小编就为大家分享一篇python绘制散点图并标记序号的方法，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧2018-12-12
echarts是百度开源的一个数据可视化JS库，主要用于数据可视化。pyecharts是一个用于生成Echarts图表的类库。实际上就是Echarts与Python的对接。本文将利用pyecharts库绘制象形柱状图，感兴趣的可以了解一下2022-01-01
这篇文章主要介绍了如何远程使用服务器上的Jupyter notebook,主要是在服务器端执行操作，需要特别注意为了防止远程中断，使用挂起操作，即执行nohup jupyter notebook，需要的朋友可以参考下2023-02-02
最新评论