python计数排序和基数排序算法实例

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python计数排序和基数排序算法实例，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2241字，纯文字阅读大概需要4分钟。

内容图文

一、计数排序

计数排序(Counting sort)是一种稳定的排序算法

算法的步骤如下：
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K)，空间复杂度为O(N+K)。当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计数排序和基数排序算法实例所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---