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

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 使用“floor division”，截断正常除法的非整数部分。

无论如何，第一个问题是你在 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!