小白学数据结构——四、排序算法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个“桶”中,合并后十位数就有序了,以此类推将得到有序数组。


欢迎点赞关注,如有疑问或错误,欢迎留言区指出。


分享给朋友:
您可能感兴趣的文章:
随机阅读: