求n个元素中最大的m个元素，其中n >>> m

最简单的解决方案，每个人都应该很明显，就是简单地做m次冒泡排序算法。

然后打印出数组的最后n个元素。

它不需要外部数据结构，并且使用了一种大家都知道的算法。

运行时间估计为O(m*n)。到目前为止最好的答案是O(nlog (m))，所以这个解决方案对于小m来说并不显着昂贵。

我并不是说这不能改进，但这是迄今为止最简单的解决方案。

我用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亿个元素。为了公平起见，我给它提供了最坏情况的输入(具有讽刺意味的是，一个已经排序的数组)。

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

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

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

I would find out who had the time to put a billion numbers into an array and fire him. Must work for government. At least if you had a linked list you could insert a number into the middle without moving half a billion to make room. Even better a Btree allows for a binary search. Each comparison eliminates half of your total. A hash algorithm would allow you to populate the data structure like a checkerboard but not so good for sparse data. As it is your best bet is to have a solution array of 100 integers and keep track of the lowest number in your solution array so you can replace it when you come across a higher number in the original array. You would have to look at every element in the original array assuming it is not sorted to begin with.

受@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个字节会有性能问题，但这只是为了举例。好的一面是，只需要很少的内存。

可能的改进。

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

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

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