0

我有一个学校项目,我需要使用不同的排序算法对所有类型的数据类型进行排序。基数排序效果很好,但它不能对除整数以外的任何东西进行排序。我可能不会为除整数以外的任何东西添加排序结果,因为每种数据类型都会被排序为整数。

也就是说,我想知道是否有更好的方法将字符串转换为整数?这是我带来的。我不想超越 python 并尝试尽可能多地使用标准函数。

def charToHex(char):
    return hex(ord(char))[2:]

def stringToHex(text):
    t = ''
    for char in text:
        t += charToHex(char)

    return t

def stringToInt(text):
    return int(stringToHex(text), 16)

print stringToInt('allo')
print stringToInt('allp')
print stringToInt('all')

它确实运作良好,但我很高兴知道是否有更好的方法来处理它。对于它的价值,使用基数排序对整数以外的任何东西进行排序听起来毫无意义。因为即使您可以对整数列表进行排序。您必须将所有键的值返回到列表中。

我本来打算做这样的事情。对于我列表中的每个值,获取一个整数键。将该键放入哈希表中,并将值放入该哈希表的列表中。用整数键替换列表中的值,然后对键列表进行排序。

对于排序列表中的每个键,获取该键的值列表并弹出一项。将该项目放入列表中并继续。

我还想知道是否有一种方法可以优化此过程,以使其值得使用基数排序而不是其他不需要任何转换的排序。列表中的项目数量可能超过 50000。

编辑

实际上这里的代码不适用于不同大小的字符串。我不太确定如何检查。用空格填充字符串似乎有效。

def getMaxLen(ls):
    lenght = 0

    for text in ls:
        lenght = max(lenght, len(text))

    return lenght

def convertList(ls):
    size = getMaxLen(ls)
    copy = ls[:]

    for i, val in enumerate(copy):
        copy[i] = stringToInt(val.ljust(size, ' '))

    return copy

print convertList(["allo", "all", "bal"])
4

1 回答 1

2

首先,看看这篇文章。那篇文章表明,是的,在某些情况下,您可以为字符串找出比任何其他排序都快的基数排序算法。

其次,更重要的是,我会问自己是否正在进行过早优化。使用 python 的功能对 50k 个项目进行排序sort()将非常快。除非您确定这是您应用程序中的瓶颈,否则我不会担心它,只会使用该sort()功能。如果它是一个瓶颈,我也会确保你没有办法避免做所有这些事情(例如缓存、处理未排序数据的算法等)

于 2013-05-06T13:33:32.047 回答