Python实现的基数排序算法原理与用法实例分析
作者:Alex Yu 发布时间:2023-11-11 10:15:12
标签:Python,基数排序,算法
本文实例讲述了Python实现的基数排序算法。分享给大家供大家参考,具体如下:
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
实现代码如下:
#-*- coding: UTF-8 -*-
import numpy as np
def RadixSort(a):
i = 0 #初始为个位排序
n = 1 #最小的位数置为1(包含0)
max = np.max(a) #得到带排序数组中最大数
while max/(10**n) > 0: #得到最大数是几位数
n += 1
while i < n:
bucket = {} #用字典构建桶
for x in xrange(0,10):
bucket.setdefault(x, []) #将每个桶置空
for x in a: #对每一位进行排序
radix =(x / (10**i)) % 10 #得到每位的基数
bucket[radix].append(x) #将对应的数组元素加入到相应位基数的桶中
j = 0
for k in xrange(0, 10):
if len(bucket[k]) != 0: #若桶不为空
for y in bucket[k]: #将该桶中每个元素
a[j] = y #放回到数组中
j += 1
i += 1
if __name__ == '__main__':
a = np.random.randint(0, 1000, size = 10)
print "Before sorting..."
print "---------------------------------------------------------------"
print a
print "---------------------------------------------------------------"
RadixSort(a)
print "After sorting..."
print "---------------------------------------------------------------"
print a
print "---------------------------------------------------------------"
运行结果:
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/biaoyu/p/4831648.html
0
投稿
猜你喜欢
- nii.gz格式是医学图像常用的压缩格式,python中可用nibabel和sitk来读取保存。使用nibabel由于使用nibabel图像
- 不知道大家有没有一种感觉,每次当使用numpy数组的时候坐标轴总是傻傻分不清楚,然后就会十分的困惑,每次运算都需要去尝试好久才能得出想要的结
- 借助 org.springframework.ui.Model 对象或 Map 对象将信息传到 springmvc 的页面中需要:jstl
- window.onload=function(){ pd(11);} function pd(number) { if(number>
- <script language="vbscript" runat="s
- 偶然看到 Tanel Poder 提到的一个 Metalink Note (438452.1): Performance Tools Qui
- 本文通过实例解析了 SQL Server 数据库扩展存储过程,实现远程备份与恢复的方法和步骤实例说明: 环境:win2k+sqlserver
- 最近在倒腾一个txt文件,因为文件太大,所以给切割成了好几个小的文件,只有第一个文件有标题,从第二个开始就没有标题了。我的需求是取出指定的列
- 经纬度坐标转换最常见办法就是调用第三方 API,例如百度、高德地图等服务平台,提供了相应的功能接口,它们的这类技术已经非常成熟啦,准确稳定,
- Python encode()方法encode() 方法为字符串类型(str)提供的方法,用于将 str 类型转换成 bytes 类型,这个
- 问题1:使用.net2005自带的SQL-Express连接不上。解决方法:1.网络防火墙阻止数据库连接;2.默认SQL-Express没有
- 从业这几年,自己写过的和帮人参谋的所谓“设计规范”不少了,这个东西大概在中国的决策层眼里是这么回事儿 - 一帮农民在一块田里种粮食,起先天气
- 最近在着手支付宝个人版改版的项目,正好在一些国内知名的SNS网站上分别注册了帐户进行体验。显然一点,国内的SNS都带有Facebook的影子
- HTML5 中 div section article 的区别刚刚开始接触 HTML5 时,对它的标签很不适应,甚至一度有点反感。尤其是对
- (1)int转strings := strconv.Itoa(i)等价于s := strconv.FormatInt(int64(i), 1
- 一个不错的文字放大特性源码。效果图:运行代码框<script for=document event=onmousemove>//
- 呵呵,这几天沉溺于灌水,发现转贴的时候真的是很不方便,文字、图形、颜色、连接,如果都转过来真的是满费劲的,于是就写了一个小东西,简陋的很,不
- Dreamweaver(以下简称DW)提供了一种称为“Behavior”(行为)的机制,帮助你构建页面
- 这里所说的“小偷”指的是在ASP中运用XML中的xmlhttp组件提供的强大功能,把远程网站上的数据(图片,网页及其他文件)抓取采集到本地,
- 本文介绍Python实现端口复用实例如下所示:#coding=utf-8import socketimport sysimport sele