我的基数排序有什么问题? [英] What is wrong with my radix sort?

问题描述

注意:我正在使用python 3.

Note: I am using python 3.

我正在尝试按字母顺序对单词列表进行排序.

I am trying to sort a list of words in alphabetical order.

这是我的排序:

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的迭代遍历整个列表.

maxL is the length of the longest words I have, so iterating from 0 to maxL goes through the entire list.

我的列表结果[]是列表列表.结果中的每个列表都包含一个单词对象，描述如下:

My list results[] is a list of lists. Each list within results contains a word object described as follows:

class word(object): #object class

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

例如，结果[3]应包含wLength为3的所有单词的列表.

For example, results[3] should contain a list of all words with wLength of 3.

当我输入整个程序时，将输入以下内容:

When I feed my entire program the following input:

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

我很确定我在打印时正确地遍历了result [].为什么我的radix_sort没有给我正确的结果?我尝试使用调试器，但没有运气.

I'm pretty sure I'm iterating through results[] correctly when printing. Why is my radix_sort not giving me the right results? I tried using the debugger but no luck.

我将代码更改如下:

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

现在在这里给我一个错误:

Now it's giving me an error here:

for containedList in buckets:

它说:"UnboundLocalError:分配前引用了局部变量'buckets'".这是什么意思?

It says "UnboundLocalError: local variable 'buckets' referenced before assignment". What does this mean?

推荐答案

在我的评论之后，看起来应该像

Following on my comments, that should look like

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)

这篇关于我的基数排序有什么问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！