内容简介:小白学数据结构——四、排序算法Python(桶、计数、基数排序)
在早些的文章中,我们讲过了常见的比较 排序 算法,详情情回顾:
小白学数据结构——四、排序算法Python(冒泡、选择、快速、插入、希尔、归并排序)那么我们这次就来看一些不是基于比较的排序算法,包括了桶排序,计数排序,基数排序。
1.桶排序
说起桶排序,就先来介绍一下我们加下来要用的桶,说的就是下面这个桶(当然不是用来装垃圾的),桶盖表示游标index,桶身上表示该游标下的数据data,没错,可以看做数组中的一个元素
假设我们需要排序数组A=【4 ,-1,0,3,3】这5个数字,我们需要怎么做呢?
把大象放进冰箱需要分几步?
1.把冰箱门打开
2.把大象装进去
3.把冰箱门关上
同样的道理,我们也需要思考三个问题:
1.我们需要多少个桶?
2.怎么把原数据放进桶里?
3.怎么把数据从桶里拿出来?
那我们需要多少个桶呢?答案是我们 max-min+1 个桶。
当然这样说不够生动,我们直接看上面的数组A,它需要 4 -(-1)+ 1= 6 个桶,就是把从-1到4的所有数全部遍历一遍共有-1,0,1,2,3,4这6个数,所以需要6个桶
我们把这么多桶也当做一个数据,它有游标(在它的桶盖上),还有数据(桶身),data中记录元素出现的次数
怎么把原来的数据装进桶里呢?实际上,桶里面装的不是A数组的元素,而是数组中元素出现的次数,比如我们C中下标为0记录A中最下的数组元素出现的次数(即-1出现的次数)。出现次数为1次,所以C[0]=1
同理,C[1]记录A中第二小的数组元素出现的次数(即0出现的次数),所以C[1]=1
我们的桶后来就变成了:
也就是说A[i]会使C[A[i] - min]的值加1。(C中下标index用A[i] - min表示)
怎么把数据从桶里拿出来?这个很简单,既然C中下标index用A[i] - min表示,那么C中的值不为0的时候,输出C[i]个i+min就好了,这样讲还是不够生动,直接来个栗子
比如当i为4的时候,C[i]的值为2,说明输出2次,输出两次的数字就是i+min,就是4+(-1)=3,即输出两个3。
这样输出的数字当然是有序的了,而且没有和其他数字进行比较。
详细代码看这里
''' 桶排序 ''' def bucket(datalist): #设置桶的大小 buckets = [0] * ((max(datalist) - min(datalist))+1) #设置桶中元素的值 for i in range(len(datalist)): buckets[datalist[i]-min(datalist)] += 1 #将桶中元素存到B,此时B有序 B=[] for i in range(len(buckets)): if buckets[i] != 0: B += [i+min(datalist)]*buckets[i] return B
上述是桶排序的一种简单形式,每个桶中元素也可以不止一个,可以将元素分配到不同数值区间,然后再该区间进行排序后输出。这又与基数排序有类似之处,建议先看完后面两中在扩展学习。
2.计数排序
计数排序,比上面的桶排序多做了一步,即得到每个桶中的数值后(数值是原数组中每个元素出现的次数),后一个数值加上它前面的一个数值,一次类推。
需要排序数组A=【4 ,-1,0,3,3】这5个数字
加出来的数值的意义就是 说截止此数值之前,包括这个数值,一共有多少元素在桶里。
这是原来桶排序中的桶:
这是加起来后的桶的情况:
此时应该怎么输出呢?
就看倒数第二个桶吧,C[4]=4,说明截止这里(包括这个元素),已经有4个原数组中值被算进去了,那么请问这里这个元素应该放在第几个位置?
答案当然是第4个位置(index为3,因为数组以0开始),创建一个新数组(和原数组A一样长),把4+min(4+min表示A中元素,别忘了我们之前说C中A[i]-min=index)放到第4个位置就行了,这就是它最终呆的位置。
如果你感觉理解起来比较吃力,请先清楚:
1.桶中存储原数组中存储的是元素出现的次数
2.怎么知道原数组中元素x出现的次数存在C的那个下标下呢?答案是index=x-min(min表示原数组最小的元素)
建议不理解的话自己在纸上画一下排序过程
代码戳这里
''' 计数排序 ''' def CountSort(datalist): #最终排好序的数组 B=[0]*len(datalist) #计算用来存储计数的数组C的长度 maxNum=max(datalist) minNum=min(datalist) cLength=maxNum-minNum+1 C=[0]*cLength #将原数组中数字出现的次数存储到C中 for i in range(len(datalist)): #datalist[i]-min表示datalist中下标为i的值应该放到C中哪个位置去 C[datalist[i]-minNum]+=1 #将C中数组元素的值(每个值出现的次数)加上前一个数字出现的次数 for i in range(1,cLength): C[i]+=C[i-1] #遍历A中元素,将它放入B中最终应该在的位置 for i in range(len(datalist)): #C[datalist[i]-minNum]表示截止datalist[i],小于等于datalist[i]的有多少 B[C[datalist[i]-minNum]-1]=datalist[i] #c中记录的值得数量应该减1,因为那个对应的元素已经到B里面了 C[datalist[i]-minNum]-=1 return B
3.基数排序
基数排序理解起来也是比较容易的,不过不要被“基数”这个名词给整蒙了,说白了,基数排序就是先将个位相同的放到一个桶里面(此时共有10个桶,分为0,1,2,3,4,5,6,7,8,9,放进桶里的都是有序的,因为拿出来的时候回先从标号为0的桶开始拿,),桶清空,然后把十位相同的放进一个桶里面,以此类推,最终得到有序的序列。
直接先来个简单的例子,假设我们要排序的数组为:
a=[10 , 23, 56 ,78 ,42 ,12, 58 , 46 ,1 ,4 , 65 ]
注意:这里为了演示所以采取了2位数的数字
第一次放进桶里面的是个位相同的,也就是:
第二次放进桶里面的十位数相同,也就是:
那么将上述数组小段合并起来组成的数组就是有序的了。
但是现在有一些细节问题需要解决:
Q:怎么知道最大的数字是多少位的呢?
K = int(math.ceil(math.log(max(a)+1, radix))) # 最大的数用几位数表示,如91用两位数表示
其中radix表示进制,默认就是采用10进制表达radix=10
得到K表示=2表示用个位和十位可以表示所有的数,即不超过三位数
Q:怎么知道个位数十位数是多少呢?
temp=int(val%(radix**i)/(radix**(i-1)))
其中i就是上面K的遍历,算个位是多少就令i=1
一个简单的例子:
import math """a为整数列表, radix为基数""" a=[10,23,56,78,42,12,58,46,1,4,65] radix=10 K = int(math.ceil(math.log(max(a)+1, radix))) # 最大的数用几位数表示,如91用两位数表示 bucket = [[] for i in range(radix)] # 不能用 [[]]*radix bucketBack = [] #桶的缓存,便于观察桶中元素的变化 for i in range(1, K+1): # K次循环,如两次循环的话,先将个位排序,在排序10位数 for val in a: temp=int(val%(radix**i)/(radix**(i-1))) print(temp,end=' ') bucket[temp].append(val) # 获得整數第K位數字 (從低到高),如91,先看个位数是1 print() del a[:] for each in bucket: a.extend(each) # 桶合并 bucketBack.append(bucket)#将目前桶中元素存储起来 bucket = [[] for i in range(radix)]#清空当前桶,便于下一次入桶
但上面的代码有一个bug,就是没法排序负数,那怎么办呢?
一种方法就是先把负数和正数分开,分别排序后合并,下面是这种思路的实现:
# -*- coding: utf-8 -*- """ Created on Mon Jan 22 12:58:35 2018 @author: liang """ import math ''' 基排序 BaseSort将数据的负数分开分别使用基排序 sort为实际排序方法 ''' #分开数据 def BaseSort(a): a_minus=[] a_positive=[] for i in range(len(a)): if a[i]<0: a_minus.append(abs( a[i])) else: a_positive.append(a[i]) a=[] if len(a_minus)>0: a_minus=sort(a_minus) a_minus.reverse() a_minus=[i*(-1) for i in a_minus] a.extend(a_minus) if len(a_positive)>0: a_positive=sort(a_positive) a.extend(a_positive) return a #排序方法 def sort(a,radix=10): K = int(math.ceil(math.log(max(a)+1, radix))) # 最大的数用几位数表示,如91用两位数表示 bucket = [[] for i in range(radix)] # 不能用 [[]]*radix bucketBack = [] #桶的缓存,便于观察桶中元素的变化 for i in range(1, K+1): # K次循环,如两次循环的话,先将个位排序,在排序10位数 for val in a: temp=int(val%(radix**i)/(radix**(i-1))) print(temp,end=' ') bucket[temp].append(val) # 获得整數第K位數字 (从低到高),如91,先看个位数是1 print() del a[:] for each in bucket: a.extend(each) bucketBack.append(bucket)#将目前桶中元素存储起来 bucket = [[] for i in range(radix)]#清空当前桶,便于下一次入桶 return a """a为整数列表, radix为基数""" a=[-12,-2,-20,10,200,-155,10000] a=BaseSort(a)
好,写到这里就差不多说完了非基于比较的排序方法了
一共讲了3种排序方法:
桶排序,计数排序的“桶”中记录了原数组元素出现的次数,扩展了空间,不用比较的方法进行排序,然后按“桶”挨个输出就好了
基数排序中,利用个位数的不同将原数组放入10个“桶”中,合并后个位数就有序了,然后再根据十位数的不同将原数组放入10个“桶”中,合并后十位数就有序了,以此类推将得到有序数组。
欢迎点赞关注,如有疑问或错误,欢迎留言区指出。
以上所述就是小编给大家介绍的《小白学数据结构——四、排序算法Python(桶、计数、基数排序)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据挖掘导论
Pang-Ning Tan、Michael Steinbach、Vipin Kumar / 范明、范宏建 / 人民邮电出版社 / 2010-12-10 / 69.00元
本书全面介绍了数据挖掘,涵盖了五个主题:数据、分类、关联分析、聚类和异常检测。除异常检测外,每个主题都有两章。前一章涵盖基本概念、代表性算法和评估技术,而后一章讨论高级概念和算法。这样读者在透彻地理解数据挖掘的基础的同时,还能够了解更多重要的高级主题。 本书是明尼苏达大学和密歇根州立大学数据挖掘课程的教材,由于独具特色,正式出版之前就已经被斯坦福大学、得克萨斯大学奥斯汀分校等众多名校采用。 ......一起来看看 《数据挖掘导论》 这本书的介绍吧!