python计数排序和基数排序算法实例
发布时间:2023-11-01 01:23:26
一、计数排序
计数排序(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)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。
它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用 * (Least significant digital)或MSD(Most significant digital), * 的排序方式由键值的最右边开始,而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 操作 PostgreSQL 数据库。分享给大家供大家参考,具体如下:我使用的是 Python 3.7.0Post
- 前言文件上传漏洞大多出现在可以进行文件上传的地方,如用户头像上传,文档上传处等。该漏洞是一个危害十分大的漏洞,通过文件上传,攻击者可以上传w
- 相关的题外话:一、操作系统window系统内部都是unicode的。文件夹名,文件名等都是unicode的,任何语言系统下都能正常显示。二、
- 本文主要跟大家分享在类unix操作系统下supervisor的使用以及一些关于进程的知识一、问题背景1、背景如何才能让一个进程摆脱终端,获得
- 左右结构是平常页面中最经常看到的结构,简洁一些的页面就会使用边框将左右两边隔开,但往往由于左右两边的内容可能是不等高的,所以就会有一高一低的
- 问题:m = re.findall('[0-9]*4[0-9]*', '[4]') 可以匹配到4.m = r
- 本文实例为大家分享了python+logging+yaml实现日志分割的具体代码,供大家参考,具体内容如下1、建立log.yaml文件ver
- 发现问题当我用pip安装好opencv-pyton后,我激动得在python项目中导入cv2就像这样:import cv2 as cvbut
- 第一次写技术博客,有不尽如人意的地方,还请见谅和指正。为什么想整理这方面的类容,我觉得就像油画家要了解他的颜料和画布、雕塑家要了解他的石材一
- has_key()方法可以检查字典中是否含有指定的键,如果有则返回True,否则就返回False。语法格式:dictionary_name.
- Selenium爬虫遇到 数据是以 JSON 字符串的形式包裹在 Script 标签中,假设Script标签下代码如下:<script
- 给网页添加打印按钮,除了打印之外,还有页面设置、打印预览、复制本文链接到剪贴板等网页基本应用。正象我在图中标注的,大部分按钮只能适用于IE浏
- python实现PSO算法优化二元函数,具体代码如下所示:import numpy as np import random import m
- gzip 是什么东东呢?百科跟我们说gzip是GNU zip的缩写,它是一个 GNU 自由软件的文件压缩程序。…gzip 的基础是 DEFL
- 论证完使用target=_blank并非绝对错误之后,分场景探讨如何减少新开窗口。自有意识注意这个问题,是看到蓝色经典Plod大叔在04年提
- 键盘事件废话不多说直接上包from selenium.webdriver.common.keys import Keys1、删除键 BACK
- 方法很简单,实现原理:使用asp的Request.ServerVariables("HTTP_REFERER") 判断来
- lambda函数是一种小的匿名函数。lambda语法lambda函数:lambda [arg1 [,arg2,...[,argn]]] :
- 本文实例为大家分享了opencv实现车牌识别的具体代码,供大家参考,具体内容如下(1)提取车牌位置,将车牌从图中分割出来;(2)车牌字符的分
- GetRows 方法 将 Recordset 对象的多个记录复制到数组中。 语法 代码如下: array = recordset.GetR