经典算法应用之七----10亿数据中取最大的100个数据

给出三种思路，仅供参考。。
1.思路一：根据快速排序划分的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。
step1：递归对所有数据分成[a,b)，(b,d]两个区间，(b,d]区间内的数都是大于[a,b)区间内的数
step2：对(b,d]重复 step1操作，直到最右边的区间个数小于100个。注意[a,b)区间不用划分
step3：返回上一个区间，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为[a2,b2)，(b2,d2]两个区间，取(b2,d2]区间。如果个数不够，继续 step3操作，如果个数超过100的就重复 step1操作，直到最后右边只有100个数为止。

复杂度为O(10亿*100)

2.思路二：先取出前100个数，维护一个100个数的最小堆，遍历一遍剩余的元素，在此过程中维护小顶堆就可以了。
具体步骤如下：
step1：取前m个元素（例如m=100），建立一个小顶堆。保持一个小顶堆得性质的步骤，运行时间为O（lgm);建立一个小顶堆运行时间为mO（lgm）=O(m lgm);
step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素小，直接丢弃；如果大于堆顶元素，则用该元素替换堆顶元素，然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素，因此需要维护堆的代价为(N-m)O(lgm); 最后这个堆中的元素就是前最大的100个。时间复杂度为O(N lgm）。

复杂度为O(10亿lg100)。
** 注：推荐采用这种算法。。*

3.采用局部淘汰法。
具体步骤如下：
step1:选取前100个元素，并排序，记为序列L。
step2:然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。

复杂度为O(10亿*100)

经典算法应用之七----10亿数据中取最大的100个数据

推荐阅读更多精彩内容