在Python 2中有效地排序10 ** 6位数字

Question

我使用long类型来存储数字并使用普通排序方法进行排序，但它不够有效。

我认为long(raw_input())花费太多时间。

有人可以想到一种有效的解决方法吗？

n = int(raw_input().strip())
unsorted = []
for i in xrange(n):
    term = long(raw_input())
    unsorted.append(term)
for i in sorted(unsorted):
    print i

Answer 1

，因为您说这是一个竞争性的编程问题，该解决方案将起作用，否则它将永远无法正常工作，因为它需要太多的内存，并且会破坏不良情况。但是在竞争性编程中，约束并不多，它应该起作用。

我们只是添加比较器，即 gt 和 lt 方法，该方法可以决定2个对象之间的比较。

class VeryBigNumber(object):
    def __init__(self,number_string):
        self.number = number_string

def __gt__(self,other):
    if len(self.number)>len(other.number):
        return True
    elif len(self.number)<len(other.number):
        return False
    for i in xrange(min(len(self.number),len(other.number))):
        if int(self.number[i])>int(other.number[i]):
            return True
        elif int(self.number[i])<int(other.number[i]):
            return False
    return False
def __eq__(self,other):
    return self.number == other.number
def __lt__(self,other):
    return not (self.__eq__(other) or self.__gt__(other))
arr = []
for i in xrange(n):
    arr.append(VeryBigNumber(raw_input().strip())
arr = sorted(arr)
for a in arr:
    print a.number,

大解释：

1. 在您说的评论中，这是为了进行编码竞赛。这向我们确保了记忆，如果足够小，我们能够在一秒钟以下阅读中阅读。

2. 我们不会将如此大的字符串转换为不必要的数字。相反，我们按原样保留字符串。

3. 我们如何对其进行分类？我们进行自己的课程并使用字符串比较。

4. 这些工作是通过比较字符串之间的字符数字，因此只有一个字符在一个非常有效的时候转换为int。

5. 我已经测试了上述代码，并且可以正常工作