TopN问题

TopN问题是Android面试中经常遇到的问题，集在一个很大的集合中找到前N大的树，如给出10亿个无序的整数集合，从中找到前100或者前1000等的数。

这种问题首先排序一定能解决，例如快速排序或者冒泡排序，这里如果实用排序算法来实现的话冒泡排序可能要优于快速排序（因此只需要找出前100或者前1000大的数即可，即使使用冒泡排序也只需要冒泡100次或者1000次即可，算法的时间复杂度是100N或者1000N，而使用冒泡排序的时间复杂度是Nlogn）。

无论是什么排序都可以实现TopN的问题，但是时间复杂度相对较高，因此可以考虑分治的思想与快速排序相结合，首先类似于快速排序算法，从中任选一个数作为标兵，然后对整个集合进行partition分区，将大于它的至于左边，小于它的至于右边如下图所示。

如果前一部分的集合的长度等于N排序结束，如果前一部分的集合的长度大于N，则从前一部分中在随机查找出一个数作为标兵，对该集合做partition分区操作；如果该集合的长度小于N，对小于标兵T2的集合做partition分区操作，判断右边大于T2的集合是否等于N-S(num>T1),以此类推

这样的话算法的时间复杂度是O(N)。

因为第一次做partition的时间复杂度一定是O(N),第二次来看数据已经减半了，以此类推，因此总的时间复杂度为O(N) = N + N / 2 + N / 2^2 +N / 2^3 +...，因此总的时间复杂度是O(N)。

实现分治算法的前提是需要有足够的内存空间，如果内存空间不够，例如只有2G的内存空间，而以Int32位来计算，10亿个数需要4G的内存空间开存储，现在不满足条件，这时就需要使用文件分别存储，

第二次再从其中一个文件中读取数据，这样的话也是可以实现的，但是缺点是需要多次磁盘的读取和写入操作，效率相对不高。

使用如果内存不足的情况下使用文件操作效率较低，因此可以考虑分布式计算，例如有1000台电脑，每一台电脑计算1百万个数中的前1000大的数，然后将这1000*1000大的数再进行排序也能实现需求，这样的好处是计算较快，缺点也很明显，需要1000台电脑。

如果只有一台电脑的时候，可以考虑使用堆排序，首先先内存中开辟出一个容量为一千的小顶堆，然后将数组中的前1000个数据放入小顶推中并排序，根据堆的性质，堆中的每一个元素都比它的左右子节点中的元素小。后面每次进入的数堆排序字对进行一次堆排序，如果插入的元素比堆顶的元素小则直接丢弃，否则将堆顶元素替换并进行堆排序，从新构成小顶堆，以此类推。当所有的数据都处理完后，剩下的堆中的元素就是所要的10亿元素中最大的前1000个数。最后以此输出堆中元素。

这种方式的优点是所有的元素都只读区一次。不存在数据多次读取的情况。