一、计数排序
计数排序(Counting sort)是一种稳定的排序算法
算法的步骤如下：
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K)，空间复杂度为O(N+K)，
python计数排序和基数排序算法实例
。当K不是很大时，这是一个很有效的线性排序算法。以下是测试代码：
复制代码代码如下:
#-*- coding:utf8 -*-
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则相反，由键值的最左边开始。
以下是一个测试用例：
复制代码代码如下:
#-*- coding:utf8 -*-
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实现排序算法
python算法学习之计数排序实例
python算法学习之基数排序实例
python算法学习之桶排序算法实例(分块排序)
python冒泡排序算法的实现代码
python选择排序算法的实现代码
python插入排序算法的实现代码
python快速排序代码实例
python实现的各种排序算法代码
python 实现堆排序算法代码
python 实现归并排序算法
python 算法 排序实现快速排序
python 快速排序代码
python3.0 字典key排序
Python学习笔记_数据排序方法
QQ空间 搜狐微博 人人网 开心网 百度搜藏更多
Tags：python 计数排序 基数排序 算法
复制链接收藏本文打印本文关闭本文返回首页
上一篇：python处理圆角图片、圆形图片的例子
下一篇：windows下wxPython开发环境安装与配置方法
相关文章
2014-05-05Python中使用动态变量名的方法
2014-01-01linux系统使用python监测网络接口获取网络的输入输出
2009-09-09python encode和decode的妙用
2013-11-11python list语法学习（带例子）
2014-01-01使用scrapy实现爬网站例子和实现网络爬虫(蜘蛛)的步骤
2014-04-04使用Python获取CPU、内存和硬盘等windowns系统信息的2个例子
2014-06-06Python中的yield浅析
2009-11-11python 文件和路径操作函数小结
2014-04-04python中精确输出JSON浮点数的方法
2013-11-11linux环境下安装pyramid和新建项目的步骤
文章评论
最 近 更 新
python的urllib模块显示下载进度示例
理解python多线程（python多线程简明教程
go和python调用其它程序并得到程序输出
python使用urllib2模块获取gravatar头像实
常用python数据类型转换函数总结
Python tempfile模块学习笔记（临时文件）
python改变日志(logging)存放位置的示例
用实例说明python的*args和**kwargs用法
天翼开放平台免费短信验证码接口使用实例
Flask SQLAlchemy一对一,一对多的使用方法
热 点 排 行
Python入门教程 超详细1小时学会
python 中文乱码问题深入分析
比较详细Python正则表达式操作指
Python字符串的encode与decode研
Python open读写文件实现脚本
Python enumerate遍历数组示例应
Python 深入理解yield
Python+Django在windows下的开发
python 文件和路径操作函数小结
python 字符串split的用法分享