小白学数据结构——四、排序算法Python（桶、计数、基数排序）

栏目: Python · 发布时间: 6年前

内容简介：小白学数据结构——四、排序算法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个桶

小白学数据结构——四、排序算法Python（桶、计数、基数排序）我们把这么多桶也当做一个数据，它有游标（在它的桶盖上），还有数据（桶身），data中记录元素出现的次数

怎么把原来的数据装进桶里呢？实际上，桶里面装的不是A数组的元素，而是数组中元素出现的次数，比如我们C中下标为0记录A中最下的数组元素出现的次数（即-1出现的次数）。出现次数为1次，所以C[0]=1

同理，C[1]记录A中第二小的数组元素出现的次数（即0出现的次数），所以C[1]=1

我们的桶后来就变成了：

小白学数据结构——四、排序算法Python（桶、计数、基数排序）也就是说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（桶、计数、基数排序）》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对码农网的支持！