如何使用队列进行基数排序？

Question

如何使用队列正确地进行基数排序？

我在用 Python 3x。

这是我尝试用队列作为容器来实现的，因为队列是一种先进先出的数据结构。

from my_queue import Queue
def rsort(n):
    '''(list of int) -> list of int
    '''
    list_length = len(n)
    val = 0
    mod = 10
    k = 1
    bin_list = []
    alist = n
    for bins in range(0,10):
        bin_list.append(Queue())

    while val == 0:
        for num in alist:
            sig_dig = num % mod
            sig_dig = int(sig_dig / k)
            bin_list[sig_dig].enqueue(num)

        if bin_list[0].size() == list_length:
            alist.append(bin_list[0].dequeue())

        else:
            mod = mod * 10
            k = k * 10            

        new_list = []
        for bins in bin_list:
            if not bins.is_empty():
                new_list.append(bins.dequeue())
            alist = new_list

        return alist

我的代码在处理小数字时运行得很好，比如：[3,2,6,5,8,7]

但是当列表中的数字变大，比如：[240, 28, 5, 18, 140, 2]

我的程序就无法正确排序了，数字会丢失，而且顺序也乱了。

我已经尝试了很多方法，但就是无法解决这个问题 :(

Answer 1

你的代码里有几个地方看起来不太对。我不太确定具体是哪个地方导致你遇到的问题，但可能这些地方都需要修正，才能得到正确的结果。

首先，简单提一下：你可以通过只用一个整数来简化逻辑，这个整数用来找到每个数字中的某一位。建议你从零开始，逐渐增加到你想要排序的位数。你可以用 sig_dig = num // 10**k % 10 来找到某个列表项的那一位数字。这里的 // 操作符让 Python 进行“向下取整除法”，也就是把普通除法的非整数部分去掉。

接下来，第一个问题是你在循环中使用了 val == 0，但你从来没有修改过 val，而且在循环结束前就返回了一个值（所以你其实只会执行一次）。你可以通过计算列表中最长值的位数来解决这个问题，方法是用 max_digits = int(math.ceil(math.log(max(lst), 10)))。然后你可以让循环变得简单很多： for k in range(max_digits):

我看到的下一个问题是，你可能没有正确地把桶里的值放回列表中。你只调用了一次 dequeue，但你应该重复调用它，直到队列为空。或者，如果我误解了你使用的 Queue API，而 dequeue 是返回所有队列的值，那么你需要用 extend 一次性把它们全部添加到列表中。

最后，我觉得你想要的结果是这样的：

import math

from my_queue import Queue

def rsort(n):
    '''(list of int) -> list of int
    '''
    bin_list = [Queue for _ in range(10)]
    max_digits = int(math.ceil(math.log(max(lst), 10))) # calculate # of digits

    for k in range(max_digits):
        for num in alist:
            sig_dig = num / 10**k % 10 # find digit's value
            bin_list[sig_dig].enqueue(num)

        n = [] # we can reuse the name `n`, rather than using a different name
        for bins in bin_list:
            while not bins.is_empty(): # loop to dequeue all values
                n.append(bins.dequeue())

    return n # the return statement is outside the loop!