使用队列的基数排序

Question

我正在尝试创建使用队列进行排序的基数排序。 我用我的队列类的代码是基本的，但它的工作原理：

class Queue: 
    def __init__(self): 
     self.items = [] 

    def isEmpty(self): 
     return self.items == [] 

    def enqueue(self, items): 
     self.items.insert(0, items) #add item to the beginning 

    def dequeue(self): 
     return self.items.pop() # remove last item 

    def peek(self): 
     return self.items[len(self.items)-1] #First in line 

    def size(self): 
     return len(self.items) 

我的理解是基数排序使用总共11个垃圾箱。 1 bin容纳一切。其他10个仓位标记为0到9.第一轮分拣开始时从主仓位中移除1个数字，然后查看那个位置上的数字，如果这个数字是0，我们将它置于零仓中，如果它是1我们把它放在一个垃圾桶里等等。我们这样做直到主容器中的所有数字都被排序在一个位置值中，然后我们将这些数字从零容器开始拉出并放回到主容器中，然后在十个位置开始处理数百个等等。这也是我的理解，基数排序只适用于所有的数据是相同的长度（或所以我已告诉我，我假设有远离这一点

到目前为止，我有这对于我的基数：

def radix(): 
    mainBin = Queue() 
    digList = [Queue()] * 10 #creates a list of 10 queues 

numberList = random.sample(range(100000,999999), 10) 
#This would normally be passed through, but this is easier for timing 
#the sort 

for num in numberList: 
    mainBin.enqueue(str(number)) 

while not mainBin.isEmpty(): 
    temporary = [] 
    number = mainBin.dequeue() 
    for digit in number: 
     temporary.append(digit) 
     if temporary[5] == '0': 
      digList[0].enqueue(temporary[5]) 

我停在第一次if语句，因为我意识到，我不得不为有有有一个数字10点的可能性6处价值10号做到这一点。这是这样长的if-elif链写出来（19行代表一个地方的价值......），但是这是第一个想到的逻辑上的问题。任何人都可以指点我一个更好的解决方案吗？

Answer 1

而不是对目标队列进行硬编码，您可以运行for循环并使用索引。

place = 6 # In this case you know it, but you could scan data to find it. 
while place >= 0: 
    while not mainBin.isEmpty(): 
     number = mainBin.dequeue() 
     digit = number[place] 
     digList[digit].enqueue(number) 

    place -= 1 


    # Reload mainBin logic goes here. 

延伸到的情况下不是每个数字串是具有相同的长度，则可以垫用零酌情（取决于小数位你在的哪一侧。）