我的基数排序有什么问题？

Question

注意：我使用的是Python 3。

我正在尝试将一个单词列表按字母顺序排序。

这是我的排序代码：

def radix_sort(List, length):
    buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    for i in range (length-1, -1, -1):    #for every letter "column"
        for word in List:    #for every word 
            index = ord(word.azWord[i])-ord('a')   #get the index of the word
            buckets[index].append(word)     #add word object to correct bucket
    List[:] = []
    for containedList in buckets:
        List.extend(containedList)

这个代码在这个循环中被使用：

for x in range(0,maxL):
    radix_sort(results[x], x)

maxL是我拥有的最长单词的长度，所以从0到maxL的循环会遍历整个列表。

我的结果列表results[]是一个包含多个列表的列表。每个内部列表包含一个单词对象，具体描述如下：

class word(object): #object class

    def __init__(self, originalWord=None, azWord=None, wLength=None):
        self.originalWord = originalWord
        self.azWord = azWord
        self.wLength = wLength

例如，results[3]应该包含所有长度为3的单词的列表。

当我给我的整个程序输入以下内容时：

hello
world
alphabetical
dog
cat
potato
stack

用这段代码：

for row in results:
    for item in row:
        print(item.originalWord)

它打印出：

cat
cat
dog
dog
dog
cat
stack
stack
world
hello
hello
stack
hello
hello
world
hello
world
world
stack
stack
world
potato
potato
potato
potato
potato
potato
alphabetical

我很确定在打印时我正确地遍历了results[]。为什么我的基数排序（radix_sort）没有给我正确的结果？我尝试使用调试工具，但没有成功。

编辑：我把代码改成了这样：

def radix_sort(List, length):
    for i in range (length-1, -1, -1): 
        for word in List:  
            buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
            index = ord(word.azWord[i])-ord('a')  
            buckets[index].append(word)   
            List[:] = []   
    for containedList in buckets:  
        List.extend(containedList)
    return List #returns an alphabetized list

现在这里出现了一个错误：

for containedList in buckets:

错误信息是“UnboundLocalError: local variable 'buckets' referenced before assignment”。这是什么意思呢？

Answer 1

在创建队列的时候，使用列表推导式。这会让你的代码更容易理解，因为没有人想去数那些空的箱子。

buckets = [[] for i in range(26)]

另外，获取桶的索引时，不用单独给一个变量赋值，可以直接把那些计算放在索引里。

buckets[((ord(letter)/10**i)%10) for letter in word]

Answer 2

for i in range (length-1, -1, -1):    #for every letter "column"
    for word in List:    #for every word 
        index = ord(word.azWord[i])-ord('a')   #get the index of the word
        buckets[index].append(word)     #add word object to correct bucket

我们来看看这段代码。在外层循环的第一次运行中，你把所有的单词放进了桶里。在第二次运行时，你又把所有的单词放进桶里，这个过程会不断重复，直到所有的循环都结束。只有在最后，你才会把桶里的单词拿出来，放回原来的列表中。

在基数排序中，每次排序时，你都需要在外层循环的每一次运行中创建一组新的桶。每当你把物品放进桶里后，你需要立即使用这些桶来重新排列列表，而不是等到最后才去做这个步骤。

Answer 3

接着我之前的评论，这应该看起来像这样

def radix_sort(List, length):
    for i in range (length-1, -1, -1):    #for every letter "column"
        # Here buckets are created for each iteration
        buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
        for word in List:    #for every word 
            index = ord(word.azWord[i])-ord('a')   #get the index of the word
            buckets[index].append(word)     #add word object to correct bucket
        # Here List is reconstructed for each iteration
        List[:] = []
        for containedList in buckets:
            List.extend(containedList)