10亿数据中找出前1000大的
转自：https://blog.****.net/o9109003234/article/details/101365271
这是经典的TopN问题，先想到的时先排序，然后取前1000个数。部分排序，只排除前1000个数即可，但这两种方法的时间复杂度都比较高。
两个思路，一个分治（速度快），一个堆排序（空间小）。
分治法
分治法，类似快速排序中的epartition的操作，随机选一个数t，然后对整个数组进行partition，会得到两部分，前一部分的数都大于t，后一部分的数都小于t。
如果说前一部分总数大于1000个，那就继续在前一部分进行partition寻找。如果前一部分的数小于1000个，那就在后一部分再进行partition，寻找剩下的数。
分治法的时间复杂度为O(n)。首先，partition的过程，时间是o(n)。我们在进行第一次partition的时候需要花费n，第二次partition的时候，数据量减半了，所以只要花费n/2，同理第三次的时候只要花费n/4，以此类推。而n+n/2+n/4+…显然是小于2n的，所以这个方法的渐进时间只有o(n)。
如果内存不够呢？
但只有一台机器的话，只能通过堆排序。
堆排序
小顶堆：每个结点的值都小于或等于其左右孩子结点的值