0

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

我正在使用 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]

我的程序不再对列表进行排序，数字最终丢失且无序。

我一直在玩我的程序，但我无法修复它:(

4

1 回答 1

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!
于 2013-03-21T13:04:20.757 回答