Python实现基数排序——队列结构_python队列数据结构

#头条创作挑战赛#

美国人口普查工作从8年缩短到6个星期的关键是使用了如下“穿孔卡片制表机”，而制表机的核心则是采用“基数排序”，该排列利用的是队列先进先出的特点，不使用比较排序。

现在小明手上有15张纸牌，每张牌上有一个数字。他首先从左到右依次抽出，以纸牌个位数为准分发，个位数相同的纸牌放在同一列上。先抽出的纸牌放在前面，后抽出的放在后面。

然后按照从左到右，从上到下的顺序，小明收回了所有的牌，效果如下所示。

第二次接龙：从左到右依次抽出，以纸牌十位数为准分发，个位数相同的纸牌放在同一列上。先抽出的纸牌放在前面，后抽出的放在后面。效果如下所示。

然后再次按照从左到右从上到下的顺序收回所有的牌，效果如下。

第三次接龙：从左到右依次抽出，以纸牌百位数为准分发，个位数相同的纸牌放在同一列上。先抽出的纸牌放在前面，后抽出的放在后面。

再次按照从左到右从上到下的顺序收回所有的牌，效果如下。

小明经过3轮发牌、收牌，现在所有的牌已经按照从小到大的顺序排列好了。思考：为什么是3轮不是5轮呢？如果最大的数字是5位，需要经过多少轮收发实现排序？

以上算法通过Python实现如下。

# 抽象队列的特征建立队列类，定义三个方法函数：进队、出队、判断是否为空
class Queue:
    def __init__(self):      #类的构造函数，这里使用列表存储队列元素
        self.items=[]
    def enQueue(self,item):       #进队的方法函数
        self.items.append(item)   #使用列表的append方法实现添加元素
    def deQueue(self):            #出队的方法函数
        return self.items.pop(0)  #使用列表的pop方法实现删除元素
    def isEmpty(self):            #判断队列是否为空的方法函数
        return self.items==[]     #比较当前队列和空列表，返回True或False

# 定义基数排序函数
def rs(al):
    mq = Queue()                      #创建一个队列类的实例mq
    rq = [Queue() for i in range(10)] #建立列表rq，存储10个元素，均为队列类型
    for i in al:                      #把列表al中的元素逐一读入mq中
        mq.enQueue(i)                 #使用进队方法读入所有元素
    k = len(str(max(al)))             #找出al中最大值的长度，比如845长度为3，为了
求数值长度需要把数值类型转换成字符串型
    for i in range(1, k + 1):         #重复k轮发牌、收牌，也就是根据需要排序列表中
    #最大数值的长度确定收发牌的轮数
        distribute(mq, rq, i)         #调用发牌函数
        gather(mq, rq)                #调用收牌函数
    al.clear()                        #清空无序列表al
    while not mq.isEmpty():           #当队列mq不为空
        al.append(mq.deQueue())       #mq元素逐个出队添加到al列表中

# 发牌函数
def distribute(mq, rq, i):
    while not mq.isEmpty():   #当mq队列不空
        a = mq.deQueue()     #mq元素逐个出队
        #把mq队列元素按第i位分发到rq列表的第i队列
        m = a % (10 ** i) // (10 ** (i - 1)) 
#这里不好理解，首先参数i是排序函数中确定的第几轮，还记得吧第一轮是按个位数为准发牌，第二轮
是十位数，第三轮是百位数，通过公式除以10的i次方求余，再整出10的i-1次方，可以取出该元素的
第i位。

#把mq队列出队的元素a添加到rq列表的第m个队列中
        rq[m].enQueue(a)

# 收牌函数
def gather(mq, rq):
    for i in rq:                 #逐个取出rq列表中的元素，也就是10个队列元素
        while not i.isEmpty():   #当列表中的元素不为空，也就是该队列不为空
            a = i.deQueue()      #把该队列中的元素出队
            mq.enQueue(a)        #把出队的元素放到mq对列中
#主程序
al = [109, 378, 28, 5, 10, 7, 21, 845, 62, 582, 91, 336, 2, 68, 32]
#以上为待排序列表al
print("原始数据：",al)     #输出原始列表
rs(al)                   #调用基数排序函数对al列表排序
print("排序后的数据：",al)  #输出排序以后的列表al

输出结果如下

原始数据： [109, 378, 28, 5, 10, 7, 21, 845, 62, 582, 91, 336, 2, 68, 32]

排序后的数据： [2, 5, 7, 10, 21, 28, 32, 62, 68, 91, 109, 336, 378, 582, 845]