2

用于实验和学习目的。我试图从一个哈希函数创建一个排序算法，该算法给出一个偏向于字符串字母顺序的值，然后理想情况下将它放在该哈希的正确位置。我试图寻找一个哈希偏向排序函数，但只找到一个整数，如果适合我的目的，那将是一个内存猪。

原因是理论上如果做得好，这个算法可以达到 O(n) 的速度或接近。

所以这是我到目前为止在 python 中所做的：

letters = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,
'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,
's':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25,
'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,
'K':10,'L':11,'M':12,'N':13,'O':14,'P':15,'Q':16,'R':17,
'S':18,'T':19,'U':20,'V':21,'W':22,'X':23,'Y':24,'Z':25}    

def sortlist(listToSort):
    listLen = len(listToSort)
    newlist = []
    for i in listToSort:
        k = letters[i[0]]
        for j in i[1:]:
            k = (k*26) + letters[j]
        norm = k/pow(26,len(i)) # get a float hash that is normalized(i think thats what     it is called)

        # 2nd part
        idx = int(norm*len(newlist)) # get a general of where it should go
        if newlist: #find the right place from idx
            if norm < newlist[idx][1]:
                while norm < newlist[idx][1] and idx > 0: idx -= 1
                if norm > newlist[idx][1]: idx += 1
            else:
                while norm > newlist[idx][1] and idx < (len(newlist)-1): idx += 1
                if norm > newlist[idx][1]: idx += 1
        newlist.insert(idx,[i,norm])# put it in the right place with the "norm" to ref     later when sorting
    return newlist

我认为第一部分很好，但第二部分需要帮助。所以 Qs 将是做这样的事情的最佳方法，或者甚至有可能从中获得 O(n) 时间（或接近那个时间）？

我对 88,000 个单词列表进行的测试大约需要 5 分钟，10,000 个单词大约需要 30 秒，随着列表计数的增加，情况变得更糟。

如果这个想法真的可行，那么我会用 C 重新编码以获得一些真正的速度和优化。

第二部分之所以存在，只是因为它可以工作-即使速度很慢，而且我想不出更好的方法来为我的一生做这件事，我想用不需要做其他循环的东西来代替它一切皆有可能。

感谢您提供的任何建议或想法。

4

1 回答 1

3

在 O(n) 中排序时：通常不能对所有输入进行排序，期间。从根本上说，这在数学上是不可能的。

这是一个很好的、简短的信息论不可能证明：要排序，你必须能够区分 n! 输入的可能顺序；为此，您必须获取 log2(n!) 位数据；为此，您需要进行 O(log (n!)) 比较，即 O(n log n)。任何声称在 O(n) 中运行的排序算法要么是在专门的数据上运行（例如，具有固定位数的数据），要么是不正确的。

实现排序算法是一个很好的学习练习，但您可能希望坚持使用现有算法，直到您对常用的概念和方法感到满意为止。如果算法不起作用，否则可能会相当令人沮丧。

学习愉快！

PS Python 的内置timsort算法在处理大量实际数据时非常出色。因此，如果您需要生产代码的通用排序算法，通常可以依靠.sort/sorted来满足您的需求。（而且，如果你能理解 timsort，你会比 90% 的 Python 使用者做得更好 :)

于 2012-09-27T08:38:41.447 回答