python - 在 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 方法来决定两个对象之间的比较。

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. 我已经测试了上面的代码，它可以正常工作