一道java面试题，20亿数字的文本排序，如何取前100？

既然是java题，这就是经典的topk问题。先取前100个数，建立一个最小堆，剩下的数依次从堆顶插入元素，同时调整堆。最后堆中的100个元素即为结果。空间复杂度为k，时间复杂度为nlogk

我说个另类的解决方案，入门程序员就能写好。一般实际工作中遇到也应该这样做。

1、用语言把所有文本数字转义为数字，然后存入数据库。

2、建立索引。

3、select 出top100，desc。

over！何必苦苦在那里写自己都搞不好的算法呢？！

有点笨的方法.:将20亿的数字分成2000（2万）个数据一段（或文件），对每组数组取1个（也可10个），直接汇总既可。也可多取再二次分组或三次分组。更多次就约准确。

对文件一次循环即可，读入一百条数据，排序并找出最大值，依次读入数据，如果小于最大值，则更新列表与最大值，循环至完。复杂度：文件读一次即O(n)，内存排序组最大O(n)*100次。有实践过更好请劈我。

这是考算法还是考解决方案？考算法大可不必2亿这么多，考解决方案的话最便宜的用hadoop简简单单就搞定了，原理是把2亿数据分布到多台机器，每台对本机的数据做top100排序，完了以后再把初次排序的结果重新分组，再次分布到各台机器上top100排序，如此循环而已

quick(array,k)

random a in array

for(n=0→a,m=array.length→a)

if(array[n]>array[a] && array[m] <array[a])

swap(array[n],array[m])

首先你要知道考题的用意在哪？这道题无非是考察你是否有优化算法的思维，追求极致性能的主观意愿。之后就要先分析一下，性能瓶颈在哪里？第一个就是大数据计算。第二是数据量足够大，会撑爆内存。第三都是文本排序，还要考虑I/O瓶颈。张嘴就说取前100，然后再比较排除的人，立马考官就会撇嘴。要我，我就先跟他喷几个词：用多核心，GPU加速，超线程，甚至是异构计算框架。先考虑加速问题！然后再说把20亿的数据分块分桶，并行计算。你都不用具体赘述后面的算法细节了，考官就会问下一题了。

20亿数字，按一个数4字节，也就10G不到，现在一般的台式机都有那么大内存，更别提服务器了。最快么就桶排序，20亿长度的数组，遍历一次，结果就出来了，其实还可以对数据做初步评估，比如20亿个数，前100，估计落在1-100000之间概率99.9%，那消耗就更小了

我作为一个外行看来，这样的方案应该可以吧:假如要找出的是排大到小的前100.那么随机抓取20亿个中的100个，然后将这100个数排序，然后将剩下的数字中逐个跟100个中的最小的比较，如果比100个中最小的小，就淘汰这个，换下一个，如果那个数比100个中的最小的大，则将这个数置换掉那个最小的，100个再排序，(这次排序就很快了)，接着再从剩余的数字中抓一个来比较，直至20亿个全部比较完，剩下的100个就是最大的前100

如果用SQL就简单多了，把数字转为表，放在columnlist列，然后执行

select

Top 100

Columnlist

Frome table name