如何在Python中用基数排序按字母顺序排序一个（非常长的）对象列表？

Question

我正在尝试用基数排序来对一个列表中的子列表进行字母顺序排序。我需要按照我创建的对象的某个属性来对这些子列表进行排序。

注意：我不能使用内置的排序方法——我必须自己写一个。我不能使用defaultdict，所以我用了列表。

我有一个叫做results[]的列表。在results[x]中，对于所有的results[]，我有另一个列表，里面包含长度为x的单词。这些单词以单词对象的形式存储，包含原始单词（originalWord）、字母顺序的单词（azWord）和单词的长度（wLength）。例如：dog, dgo, 3。

因为我有很多很多单词，所以我决定使用基数排序，这样对我来说效率最高。我对Python还比较陌生，所以在写代码时遇到了一些问题。我有一个大致的框架，但希望能得到帮助来修正语法。

我打算在一个循环中使用radix_sort，这个循环会遍历results[]。我有一个变量maxL，用来存储我拥有的最长单词（也就是results中的列表数量）。

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

这是我尝试为字符串编写基数排序的代码。请注意，azWord属性被表示为字符列表。

def radix_sort(List, length):
    buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    for i in range (0, length-1):    #for every letter "column"
        for word in List:    #for every word 
            index = ord(word[i].azWord)-ord('a')   #get the index of the word
            buckets[index].append(word)     #add word object to correct bucket
    for containedList in buckets:
        while(containedList):
            #I'm having trouble here with emptying the lists back into the bins

编辑：另外，由于我不想耗尽内存（这是针对一个非常长的单词列表），我是否应该在进行过程中清理一些不需要的东西？

此外，目前，Eclipse给我这个错误：“Expected:: Expected::”在这一行：

for i in range (0, length-1)

当前版本：

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)

Answer 1

我觉得你在这些行上漏掉了一些冒号：

for i in range (0, length-1)  # Need a colon here

for word in List  # Need a colon here

for containedList[] in buckets  # Need a colon here

while(containedList[])  # Need a colon here

Answer 2

要把排序后的结果放回列表里：

List[:] = []
for containedList in buckets:
    List.extend(containedList)

还有一点，如果你想要正确的排序，记得要从最不重要的开始排到最重要的：

for i in range(length-1, -1, -1):

注意，你原来的范围设置其实是错的，结束点是不包括在范围内的，所以停在 length-1 会漏掉最后一个字母。