用Python解决RADIX-SORT

用radix-sort解决一个每个元素含有三个字符的列表排序问题。

“illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.”

分析

1. 每个元素由3个字符组成
2. 每个字符都为大写的A-Z

思路

1. 创建一个列表内含26个空的列表
2. 利用python的特性，从倒数开始排序(index = -1)
3. 获取每个元素的某个字符，转换成aciss，再放到相应的列表里
4. 按顺序取出每个list里的字符串，赋值给源列表
5. 循环3次以上步骤，最后输出即可得到radix-sort后的列表

代码

list = ["COW", "DOG", "SEA", "RUG", "MOB",
        "BOX", "TAB", "BAR", "EAR", "TAR",
        "DIG", "BIG", "TEA", "NOW", "FOX"]

result = [[] for _ in range(26)]
start = -1
temp = []

for x in range(3):
    for word in list:
        result[ord(word[start]) - 65].append(word)

    for chars in result:
        for x in chars:
            if x != []:
                temp.append(x)

    list = temp
    temp = []
    result = [[] for _ in range(26)]

    start -= 1

print(list)