Top K问题

1、在一组非常大量的数据中找出前100大的数据

（1）每次选出101个数进行排序，最后一个数删除，多次排序（垃圾算法，时间复杂度高）

package com.zhangrui.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 张睿
 * @date 2018/11/17 9:24
 */
public class Top100 {
    public static void main(String[] args) {
        long[] arr=new long[101];
        Random r=new Random();
        for(int i=0;i<100000;i++){
            arr[0]=r.nextLong();
            Arrays.sort(arr);
        }
        for(int i=1;i<arr.length;i++){
            long l=arr[i];
            System.out.println(l);
        }
    }
}

（2）大顶堆，优先队列 PriorityQueue，建立一个大小为K的队列（可以直接使用java中的优先队列 PriorityQueue，基于优先级堆的极大优先级队列，队列中元素默认按照自然顺序排序，数字就是默认最小的放在队列头）如果队列中有空位可以直接添加元素，如有元素个数达到K，将要添加的元素与优先队列中的队首（也就是优先队列中最小的数）进行比较，选出最小的元素放在队列头

时间复杂度为O(nlogk)
队列中方法说明：

**offer()**方法往队列添加元素如果队列已满直接返回false,队列未满则直接插入并返回true

**add()**方法是对offer()方法的简单封装.如果队列已满,抛出异常new IllegalStateException(“Queue full”);

**put()**方法往队列里插入元素,如果队列已经满,则会一直等待直到队列为空插入新元素,或者线程被中断抛出异常 **remove()**方法直接删除队头的元素:

**peek()**方法直接取出队头的元素,并不删除.

**element()**方法对peek方法进行简单封装,如果队头元素存在则取出并不删除,如果不存在抛出异常NoSuchElementException()

**poll()**方法取出并删除队头的元素,当队列为空,返回null

**take()**方法取出并删除队头的元素,当队列为空,则会一直等待直到队列有新元素可以取出,或者线程被中断抛出异常

package com.zhangrui.sort;

import java.util.*;

/**
 * @author 张睿
 * @date 2018/11/17 11:30
 * 使用固定容量的优先队列实现TopK问题
 */
public class Top100Test02 {
    private PriorityQueue<Integer> queue;
    private int k;//最大容量
    public Top100Test02(int maxSize){
        if (maxSize<0){
            throw new IllegalArgumentException();
        }
        this.k=maxSize;
        this.queue=new PriorityQueue<>(maxSize);
    }

    public void addElement(Integer e){
        if (queue.size()<k){
            queue.add(e);
        }else {
            Integer peek=queue.peek();//取得堆中最小元素
            if(e<peek){
                queue.poll();
                queue.add(e);
            }
        }
    }
    public static void main(String[] args) {
        final Top100Test02 TopQueue=new Top100Test02(10);//返回前十位
        Random random=new Random();
        int rNum=0;
        System.out.println("100个0~999之间的随机数");
        for (int i=1;i<=100;i++){
            rNum=random.nextInt(1000);
            TopQueue.addElement(rNum);
        }
        while (!TopQueue.queue.isEmpty()){
            System.out.println(TopQueue.queue.poll());
        }
    }
}

（2）针对Top K最有效的算法是BFPRT算法（中位数的中位数算法）

将n个元素每5个分为一组，分为n/5组，最后一组元素为n%5，有效组为n/5.
取出每一组的中位数，最后一个组的不用计算中位数，任意排序方法
将各组的中位数与数组开头的数据在组的顺序依次交换，这样每组的中位数就排在了每组数据的最左边
‘递归调用中位数选择算法查找出所有中位数的中位数，设为X，偶数个中位数的情况下设定为选取中间小的一个
按照X大小划分，大于或等于X的在X右边，小于X放在X左边
得到X元素的下标i，i左边的元素都小于X，i右边的元素都大于或等于X

若i==k，返回X

若i<k，在小于X元素中递归查找第i小的元素

若i>k，在大于等于X元素中递归查找第i-k小的元素

package com.zhangrui.sort;

import java.util.Random;

/**
 * @author 张睿
 * @date 2018/11/17 15:58
 * BFPRT算法
 */
public class Top100Test03 {
    private static int[] a=null;
    //冒泡排序
    public static void sort(int first,int end){
        for(int flag=first;flag<end;flag++){
            for(int i=end;i>flag;i--){
                if(a[i]<a[i-1]){
                    int t=a[i];
                    a[i]=a[i-1];
                    a[i-1]=t;
                }
            }
        }
    }
    //求最小的k个数
    //数组a中从a[p]到a[r]的元素按照x划分
    public static int partitionModify(int p,int r,int x){
        int i,j;
        for(i=p,j=r;i<j;i++){
            if(a[i]>=x){
                while (i<j&&a[j]>=x){
                    j--;
                }
                if(i!=j){
                    int t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                    j--;
                }else {
                    break;
                }
            }
        }
        if(a[i]>=x&&i>p){
            return i-1;
        }
        return i;
    }

    //将r-p+1个元素按5个元素分为一组，分别找出各组的中位数
    //再通过迭代求出中位数的中位数
    public static int selectModify(int p,int r,int k){
        int i;
        if(r-p+1<=5){
            sort(p,r);
            return a[p+k-1];
        }
        //找出中位数
        for(i=0;i<(r-p+1)/5;i++){
            int s=p+5*i,t=s+4;//获得所划分的组中头元素和尾元素的下标
            sort(s,t);//组内排序
            int temp=a[p+i];//将中位数放在组内首元素位置
            a[p+i]=a[s+2];
            a[s+2]=temp;
        }
        int x=selectModify(p,p+(r-p+1)/5-1,(r-p+6)/10);
        i=partitionModify(p,r,x);
        int j=i-p+1;
        if (k <= j) {
            return selectModify(p, i, k);
        }
        else {
            return selectModify(i + 1, r, k - j);
        }
    }

    public static void main(String[] args) {
        Random random=new Random();
        System.out.println("100个0~999之间的随机数");
        for (int i=0;i<100;i++){
           a[i]=random.nextInt(1000);
        }
        System.out.println(selectModify(0,99,10));
    }
}