我该如何对一百万个数字进行排序，并且仅在Python中打印前十个数字？

Question

我有一个包含一百万个数字的文件。我需要知道如何有效地对其进行排序，以免使计算机停滞不前，并且仅打印前十名。

#!/usr/bin/python3

#Find the 10 largest integers
#Don't store the whole list

import sys

def fOpen(fname):
        try:
                fd = open(fname,"r")
        except:
                print("Couldn't open file.")
                sys.exit(0)
        all = fd.read().splitlines()
        fd.close()
        return all

words = fOpen(sys.argv[1])

big = 0
g = len(words)
count = 10

for i in range(0,g-1):
        pos = i
        for j in range(i+1,g):
                if words[j] > words[pos]:
                        pos = j
                if pos != i:
                        words[i],words[pos] = words[pos],words[i]
                count -= 1
                if count == 0:
                        print(words[0:10])

我知道这是选择排序，我不确定什么是最好的排序。

Answer 1

如果只需要前10个值，则浪费大量时间对每个数字进行排序。

只需浏览数字列表，并跟踪到目前为止看到的前10个最大值。在浏览列表时更新前十名，并在到达末尾时将其打印出来。

这意味着您只需要对文件进行一次遍历（即theta（n）的时间复杂度）

一个更简单的问题

您可以将您的问题看成是在数字列表中找到最大值的概括。如果被给予{2,32,33,55,13, ...}并被要求寻找最大的价值，您会怎么做？典型的解决方案是浏览列表，同时记住迄今为止遇到的最大数字，并将其与下一个数字进行比较。

为了简单起见，让我们假设我们正在处理正数。

Initialize max to 0
0 < 2, so max = 2
2 < 32, so max = 32
32 < 33, so max = 33
33 < 55, so max = 55
55 > 13, so max = 55
...
return max

因此，您看到，我们可以在列表的单个遍历中找到最大值，这与任何类型的比较排序相反。

泛化

在列表中查找 前10个 值非常相似。唯一的区别是我们需要跟踪前10名，而不只是最大值（前1名）。

底线是您需要一些容纳10个值的容器。当您遍历庞大的数字列表时，在大小为10的容器中关心的唯一值是最小值。这是因为，如果您发现了一个新号码，该号码应该排在前十名之内，那么它将被替换。

无论如何，事实证明最适合快速查找分钟的数据结构是一个最小堆。但是我不确定您是否了解堆，而将堆用于10个元素的开销可能会超过其好处。

任何容纳10个元素并可以在合理的时间内获得最小值的容器都是一个好的开始。