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

yipeiwu_com5年前Python基础

一、计数排序

计数排序(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)


相关文章

Numpy截取指定范围内的数据方法

如下所示: lst = [[1,2,3,4,5,6], [7,8,9,10,11,12], [71,81,91,101,111,121]] arr = np.asarray(lst)...

Python实现个人微信号自动监控告警的示例

Python实现个人微信号自动监控告警的示例

wechat_sender 是基于 wxpy 和 tornado 实现的一个可以将你的网站、爬虫、脚本等其他应用中各种消息 (日志、报警、运行结果等) 发送到微信的工具。 运行环境 Py...

django实现登录时候输入密码错误5次锁定用户十分钟

django实现登录时候输入密码错误5次锁定用户十分钟

在学习django的时候,想要实现登录失败后,进行用户锁定,切记录锁定时间,在网上找了很多资料,但是都感觉不是那么靠谱,于是乎,我开始了我的设计,其实我一开始想要借助redis呢,但是想...

如何基于pythonnet调用halcon脚本

如何基于pythonnet调用halcon脚本

这篇文章主要介绍了如何基于pythonnet调用halcon脚本,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 最近的项目中遇到了使用...

Python列表(List)知识点总结

序列是Python中最基本的数据结构。序列中的每个元素都分配一个数字 - 它的位置,或索引,第一个索引是0,第二个索引是1,依此类推。 Python有6个序列的内置类型,但最常见的是列...