使用队列进行基数排序

Question

我正在尝试创建一个使用队列进行排序的基数排序。我用于我的队列 class 的代码是基本的，但它有效：

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 个 bin。 1 个箱子可装下所有东西。其他 10 个 bin 标记为 0 到 9。第一轮排序首先从主 bin 中删除 1 个数字，然后查看个位的数字，如果该数字是 0，我们将它放在零 bin 中，如果它是1 我们把它放在一个箱子里等等。我们这样做，直到主容器中的所有数字都按个位值排序，然后我们从零容器中取出这些数字并将它们放回主容器中，然后从十位重新开始这个过程数百等等。据我了解，基数排序仅在所有数据长度相同时才有效（或者有人告诉我。我假设周围有一些东西。

到目前为止，我的 Radix 有这个：

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.

要扩展到并非每个数字串的长度都相同的情况，您可以适当地用零填充（取决于您在小数点的哪一侧。）

使用队列进行基数排序

Radix Sorting using using Queues

python

queue

radix-sort