python计数排序和基数排序算法实例_python教程-查字典教程网
python计数排序和基数排序算法实例
python计数排序和基数排序算法实例
发布时间:2016-12-28 来源:查字典编辑
摘要:一、计数排序计数排序(Countingsort)是一种稳定的排序算法算法的步骤如下:找出待排序的数组中最大和最小的元素统计数组中每个值为i的...

一、计数排序

计数排序(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学习
    脚本专栏子分类