基于python进行桶排序与基数排序的总结
作者:笛在月明 发布时间:2023-06-13 17:32:33
本文首先举例阐述了两种排序方法的操作步骤,然后列出了用python进行的实现过程,最后对桶式排序方法的优劣进行了简单总结。
一、桶排序:
排序一个数组[5,3,6,1,2,7,5,10]
值都在1-10之间,建立10个桶:
[0 0 0 0 0 0 0 0 0 0] 桶
[1 2 3 4 5 6 7 8 9 10] 桶代表的值
遍历数组,第一个数字5,第五个桶加1
[0 0 0 0 1 0 0 0 0 0]
第二个数字3,第三个桶加1
[0 0 1 0 1 0 0 0 0 0]
遍历后
[1 1 1 0 2 1 1 0 0 1]
输出
[1 2 3 5 5 6 7 10]
代码:
def bucket_sort(lst):
buckets = [0] * ((max(lst) - min(lst))+1)
for i in range(len(lst)):
buckets[lst[i]-min(lst)] += 1
res=[]
for i in range(len(buckets)):
if buckets[i] != 0:
res += [i+min(lst)]*buckets[i]
return res
二、基数排序:
例如,对如下数据序列进行排序。
192,221,12,23
可以观察到它的每个数据至多只有3位,因此可以将每个数据拆分成3个关键字:百位(高位)、十位、个位(低位)。如果按照习惯思维,会先比较百位,百位大的数据大,百位相同的再比较十位,十位大的数据大;最后再比较个位。基数排序方法对任一子关键字排序时必须借助于另一种排序方法,而且这种排序方法必须是稳定的。对于多关键字拆分出来的子关键字,它们一定位于0-9这个可枚举的范围内,这个范围不大,因此用桶式排序效率非常好。
代码:
from random import randint
def radix_sort(lis,d):
for i in xrange(d):#d轮排序
s = [[] for k in xrange(10)]#因为每一位数字都是0~9,故建立10个桶
for j in lis:
s[j/(10**i)%10].append(i)
li = [a for b in s for a in b]
return li
对数组中的元素按照从低位到高位排序,对于[192,221,12,23]第一轮按照个位数字相同的放在一组,是s[1] =[221],s[2]=[192,12],s[3]=23,第二轮按照十位数字进行排序,s[1]=[12],s[2]=[221,23],s[9]=[192],第三轮按照百位数字进行排序,s[0]=[12,23],s[1]=[192],s[2]=[221]
总结:
桶排序与基数排序常作为桶式排序出现,基数排序进行了多轮的桶排序。桶式排序不再是一种基于比较的排序方法,它是一种比较巧妙的排序方式,但这种排序方式需要待排序的序列满足以下两个特征:待排序列所有的值处于一个可枚举的范围之类;待排序列所在的这个可枚举的范围不应该太大,否则排序开销太大。可以用于学生成绩的排序,因为在若干学生中成绩的范围仅在100以内。
桶式排序的空间开销较大,它需要两个数组,第1个buckets数组用于记录“落入”各桶中元素的个数,进而保存各元素在有序序列中的位置,第2个数组用于缓存待排数据。它只能排整形数组。而且当k较大,而数组长度n较小,即k>>n时,辅助数组C[k+1]的空间消耗较大。
来源:https://blog.csdn.net/iqqiqqiqqiqq/article/details/54837711
猜你喜欢
- 在内容为主的网站中,搜索框往往是最常用的设计元素之一。从可用性的角度来看,搜索功能是用户有了明确的内容想看的时候最后使用的功能。如果一个网站
- 说明:本文内容都是从Google上搜索来的,本想上http://www.alexa.com/查官方数据,访问非常慢暂且没查。使用本接口将返回
- 这篇文章主要介绍了python的time模块和datetime模块实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参
- 此程序主要是针对某个目录下的全部文件进行筛选,会删除重复的文件。原理很简单,会计算每个文件的哈希,将哈希存入一个字典,文件名对应哈希。imp
- <?php function BigEndian2Int($byte_word, $signed = false) { $int_va
- 这个问题好像在各种数据库中都存在,该如何处理呢?一、SQL中:sql="CREATE TABLE phone&
- 新建图像文件后选Channels面板,新建Alpha1通道; 做压
- 我就废话不多说啦,还是直接看代码吧!import osimport sysimport djangosys.path.append(r
- 字体的处理在网页设计中无论怎么强调也不为过, 毕竟网页使用来传递信息的, 而最经典最直接的信息传递方式就是文字,&nbs
- 普通方法:爬取梨视频import reimport timeimport randomimport requestsfrom lxml im
- 概述路由是自定义url地址执行指定的函数,良好的路由定义可以对seo起到很好的效果。1. 基本路由gin框架封装了http库,提供了 GET
- 想买mate40,但总是抢不到,所以想试着能不能写个脚本代码。第一步:把想要抢购的商品加进购物车,注意:脚本是对购物车内全部商品进行下单操作
- Python 实现删除某路径下文件及文件夹的脚本#!/usr/bin/env pythonimport osimport shutildel
- 二进制数据结构Struct在C/C++语言中,struct被称为结构体。而在Python中,struct是一个专门的库,用于处理字节串与原生
- 实例如下所示:# -*- coding: utf-8 -*-#to find where use the table on xxxxx xx
- 表单在网页中主要负责数据采集功能。一个表单有三个基本组成部分: 表单标签:这里面包含了处理表单数据所用CGI程序的URL以及数
- 又从 James Padolsey 这里得到个好的点子。在实际写脚本过程中可能有段 Javascript 和 HTML 非常相关(比如实例化
- 本文实例为大家分享了python实现用户名密码校验的具体代码,供大家参考,具体内容如下需要实现功能输入用户名密码 ;认证成功后显示 欢迎信息
- 1.在使用MySQL和php的时候出现过中文乱码问题(1) 只要是gb2312,gbk,utf8等支持多字节编码的字符集都可以储存汉字,当然
- 前言:pandas 中的索引意味着只需从系列中选择特定数据。索引可能意味着选择所有数据,其中一些数据来自特定列。索引也可以称为子集选择。使用