受@ron teller回答的启发，这里有一个简单的C程序来做你想做的事情。

#include <stdlib.h>
#include <stdio.h>

#define TOTAL_NUMBERS 1000000000
#define N_TOP_NUMBERS 100

int 
compare_function(const void *first, const void *second)
{
    int a = *((int *) first);
    int b = *((int *) second);
    if (a > b){
        return 1;
    }
    if (a < b){
        return -1;
    }
    return 0;
}

int 
main(int argc, char ** argv)
{
    if(argc != 2){
        printf("please supply a path to a binary file containing 1000000000"
               "integers of this machine's wordlength and endianness\n");
        exit(1);
    }
    FILE * f = fopen(argv[1], "r");
    if(!f){
        exit(1);
    }
    int top100[N_TOP_NUMBERS] = {0};
    int sorts = 0;
    for (int i = 0; i < TOTAL_NUMBERS; i++){
        int number;
        int ok;
        ok = fread(&number, sizeof(int), 1, f);
        if(!ok){
            printf("not enough numbers!\n");
            break;
        }
        if(number > top100[0]){
            sorts++;
            top100[0] = number;
            qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function);
        }

    }
    printf("%d sorts made\n"
    "the top 100 integers in %s are:\n",
    sorts, argv[1] );
    for (int i = 0; i < N_TOP_NUMBERS; i++){
        printf("%d\n", top100[i]);
    }
    fclose(f);
    exit(0);
}

在我的机器上(具有快速SSD的core i3)，它需要25秒，并进行1724种排序。 我用dd if=/dev/urandom/ count=1000000000 bs=1生成了一个二进制文件。

显然，一次只从磁盘读取4个字节会有性能问题，但这只是为了举例。好的一面是，只需要很少的内存。

首先取1000个元素并将它们添加到一个max堆中。现在取出前最多100个元素并将其存储在某个地方。现在从文件中选择接下来的900个元素，并将它们与最后100个最高的元素一起添加到堆中。

一直重复这个过程，从堆中取出100个元素，从文件中添加900个元素。

从100个元素中最后选出的100个元素将从10亿个数字中选出最大的100个元素。

我看到了很多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.

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

可能的改进。

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

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

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

Time ~ O(100 * N)
Space ~ O(100 + N)

创建一个包含100个空槽的空列表 对于输入列表中的每个数字: 如果数字小于第一个，跳过 否则用这个数字代替它 然后，将数字通过相邻的交换;直到它比下一个小 返回列表

注意:如果log(input-list.size) + c < 100，那么最佳的方法是对输入列表进行排序，然后拆分前100项。

两个选择:

(1)堆(priorityQueue)

维护最小堆的大小为100。遍历数组。一旦元素小于堆中的第一个元素，就替换它。

InSERT ELEMENT INTO HEAP: O（log100）
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)

(2)映射-约简模型。

这与hadoop中的单词计数示例非常相似。 映射工作:计算每个元素出现的频率或次数。 减约:获取顶部K元素。

通常，我会给招聘人员两个答案。他们喜欢什么就给什么。当然，映射缩减编码会很费事，因为您必须知道每个确切的参数。练习一下也无妨。 祝你好运。