我看到了很多O(N)的讨论，所以我提出了一些不同的想法。

关于这些数字的性质有什么已知的信息吗?如果答案是随机的，那就不要再进一步了，看看其他答案。你不会得到比他们更好的结果。

However! See if whatever list-populating mechanism populated that list in a particular order. Are they in a well-defined pattern where you can know with certainty that the largest magnitude of numbers will be found in a certain region of the list or on a certain interval? There may be a pattern to it. If that is so, for example if they are guaranteed to be in some sort of normal distribution with the characteristic hump in the middle, always have repeating upward trends among defined subsets, have a prolonged spike at some time T in the middle of the data set like perhaps an incidence of insider trading or equipment failure, or maybe just have a "spike" every Nth number as in analysis of forces after a catastrophe, you can reduce the number of records you have to check significantly.

不管怎样，还是有一些值得思考的东西。也许这会帮助你给未来的面试官一个深思熟虑的回答。我知道，如果有人问我这样一个问题来回应这样的问题，我会印象深刻——这将告诉我，他们正在考虑优化。只是要认识到，优化的可能性并不总是存在的。

虽然其他的quickselect解决方案已经被否决，但事实是quickselect将比使用大小为100的队列更快地找到解决方案。在比较方面，Quickselect的预期运行时间为2n + o(n)。一个非常简单的实现是

array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
  if(array[i]>r)
     add array[i] to result

这平均需要3n + o(n)次比较。此外，quickselect将数组中最大的100个项保留在最右边的100个位置，这可以提高效率。所以实际上，运行时间可以提高到2n+o(n)。

有一个问题是，这是预期的运行时间，而不是最坏的情况，但通过使用一个不错的主元选择策略(例如，随机选择21个元素，并选择这21个元素的中位数作为主元)，那么比较的数量可以保证高概率为(2+c)n对于任意小的常数c。

事实上，通过使用优化的抽样策略(例如随机抽样平方根(n)个元素，并选择第99百分位数)，对于任意小的c(假设K，要选择的元素数量为o(n))，运行时间可以降至(1+c)n + o(n)。

另一方面，使用大小为100的队列将需要O(log(100)n)个比较，log以2为底100的对数大约等于6.6。

如果我们从更抽象的意义上考虑这个问题，即从大小为N的数组中选择最大的K个元素，其中K=o(N)，但K和N都趋于无穷大，那么快速选择版本的运行时间将是o(N)，队列版本的运行时间将是o(N log K)，因此在这种意义上，快速选择也渐近地更好。

在注释中，提到队列解决方案将在随机输入的预期时间N + K log N内运行。当然，随机输入假设永远不会成立，除非问题明确地说明了这一点。队列解决方案可以以随机顺序遍历数组，但这将产生对随机数生成器的N次调用的额外成本，以及排列整个输入数组或分配一个长度为N的包含随机索引的新数组。

如果问题不允许您移动原始数组中的元素，并且分配内存的成本很高，因此不能复制数组，那就是另一回事了。但严格地从运行时间来看，这是最好的解决方案。

可能的改进。

如果文件包含十亿的数字，读取它可能会很长…

为了提高工作效率，你可以:

将文件分成n个部分，创建n个线程，让n个线程在各自的部分中寻找最大的100个数字(使用优先级队列)，最后得到所有线程输出的最大的100个数字。 使用像hadoop这样的解决方案，使用集群来完成这样的任务。在这里，您可以进一步分割文件，并更快地输出10亿(或10^12)个数字的文件。

我用Python写了一个简单的解决方案，以防有人感兴趣。它使用bisect模块和一个临时返回列表，它保持排序。这类似于优先级队列实现。

import bisect

def kLargest(A, k):
    '''returns list of k largest integers in A'''
    ret = []
    for i, a in enumerate(A):
        # For first k elements, simply construct sorted temp list
        # It is treated similarly to a priority queue
        if i < k:
            bisect.insort(ret, a) # properly inserts a into sorted list ret
        # Iterate over rest of array
        # Replace and update return array when more optimal element is found
        else:
            if a > ret[0]:
                del ret[0] # pop min element off queue
                bisect.insort(ret, a) # properly inserts a into sorted list ret
    return ret

使用100,000,000个元素和最坏情况输入是一个排序列表:

>>> from so import kLargest
>>> kLargest(range(100000000), 100)
[99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907,
 99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915,
 99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923,
 99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931,
 99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939,
 99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947,
 99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955,
 99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963,
 99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971,
 99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979,
 99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987,
 99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995,
 99999996, 99999997, 99999998, 99999999]

我花了40秒计算1亿个元素，所以我不敢计算10亿个元素。为了公平起见，我给它提供了最坏情况的输入(具有讽刺意味的是，一个已经排序的数组)。

一个非常简单的解决方案是遍历该数组100次。也就是O(n)

每次取出最大的数字(并将其值更改为最小值，以便在下一个迭代中看不到它，或者跟踪以前答案的索引(通过跟踪索引，原始数组可以有多个相同的数字))。经过100次迭代，就得到了最大的100个数字。

我知道这可能会被埋没，但这是我对一个基MSD的变化的想法。

伪代码:

//billion is the array of 1 billion numbers
int[] billion = getMyBillionNumbers();
//this assumes these are 32-bit integers and we are using hex digits
int[][] mynums = int[8][16];

for number in billion
    putInTop100Array(number)

function putInTop100Array(number){
    //basically if we got past all the digits successfully
    if(number == null)
        return true;
    msdIdx = getMsdIdx(number);
    msd = getMsd(number);
    //check if the idx above where we are is already full
    if(mynums[msdIdx][msd+1] > 99) {
        return false;
    } else if(putInTop100Array(removeMSD(number)){
        mynums[msdIdx][msd]++;
        //we've found 100 digits here, no need to keep looking below where we are
        if(mynums[msdIdx][msd] > 99){
           for(int i = 0; i < mds; i++){
              //making it 101 just so we can tell the difference
              //between numbers where we actually found 101, and 
              //where we just set it
              mynums[msdIdx][i] = 101;
           }
        }
        return true;
    }
    return false;
}

函数getMsdIdx(int num)将返回最高位(非零)的下标。函数getMsd(int num)将返回最高位。函数removeMSD(int num)将从一个数字中删除最有效的数字并返回该数字(如果删除最有效的数字后什么都没有留下，则返回null)。

完成后，剩下的就是遍历mynums以获取前100位数字。这大概是这样的:

int[] nums = int[100];
int idx = 0;
for(int i = 7; i >= 0; i--){
    int timesAdded = 0;
    for(int j = 16; j >=0 && timesAdded < 100; j--){
        for(int k = mynums[i][j]; k > 0; k--){
            nums[idx] += j;
            timesAdded++;
            idx++;
        }
    }
}

我需要注意的是，尽管上面的图看起来时间复杂度很高，但实际上它只有O(7*100)左右。

快速解释一下这是为了做什么: 从本质上讲，这个系统试图基于数字中数字的索引和数字的值来使用2d数组中的每个数字。它使用这些值作为索引来跟踪数组中插入了多少数值。当达到100时，它会关闭所有“较低的分支”。

这个算法的时间大概是O(十亿*log(16)*7)+O(100)。我可能是错的。此外，这很可能需要调试，因为它有点复杂，我只是把它写在我的头上。

编辑:没有解释的反对票是没有帮助的。如果你认为这个答案不正确，请留下评论。我很确定，StackOverflow甚至告诉你这样做，当你向下投票。