内容简介：小白学数据结构——四、排序算法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（桶、计数、基数排序）》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
