如何在大量数据中，比如百万级别，查找到第n大的数据，或者前n大的数据？

我们前面介绍了排序中常用的快排和归并排序快排和归并排序，但是快排和归并排序是全排序，对于我们的问题来说，有点浪费资源，那有没有不需要全排序但是也能解决问题的算法呢？

1、查找到第n大的数据

1.1思想

利用快排思想，对数组先进行一趟快排，把数组按降序排序的方式分成三部分，
第一部分：arr[0，p-1] ——都是比arr[p]大的值，p为数组下标
第二部分：arr[p]
第三部分：arr[p+1，arr.length-1]——都是比arr[p]小的值

如果n= p+1，那么arr[p]就是第n大的值；
如果n< p+1，说明第n大数据在第一部分中，那么只需要对第一部分数据arr[0，p-1] 再进行快排；
如果n> p+1，说明第n大数据在第三部分中，那么只需要对arr[p+1,arr.length-1]进行快排；

这其实是利用了分区的思想，只对需要的数据进行排序，而不是全排序大大提高了性能。

1.2算法

    @Test
    public void test4(){
        int[] input ={2,5,8,6,4,1,2,4,1,4,10,1,5,4,1,4,5,1,-2,5,2,4,5,5,2,100,4};
        int k = 3;
        System.out.println(sort1(input,k));
    }
    //从大到小排序
    private int sort1(int[] nums, int left, int right, int k){
        int base = nums[left];
        int leftt = left;
        int rightt = right;
        while(leftt < rightt){
            while (leftt < rightt && nums[rightt]<=base){
                rightt--;
            }

            while( leftt < rightt && nums[leftt] >= base){
                leftt++;
            }

            if(leftt < rightt){
                int temp = nums[leftt];
                nums[leftt] = nums[rightt];
                nums[rightt] = temp;
            }
            System.out.println(Arrays.toString(nums));
        }

        nums[left] = nums[leftt];
        nums[leftt] = base;
        System.out.println(Arrays.toString(nums));
        System.out.println("======lefftt="+leftt);

        if( k == leftt+1){
            return nums[leftt];
        }
         if( k < leftt+1){
            return sort1(nums,0,leftt-1,k);
        }else if( k > leftt+1){
            return sort1(nums,leftt+1,nums.length-1,k);
        }
        return -1;
    }

2、查找到前n大的数据（TopN）

在大数据中TopN问题是经常都会遇到的，比如有1亿个浮点数，如果找出其中最大的10000个？？

2.1 思想

• 分治法
  将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的10010000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。参考上面的找出第n大数字，就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^64=4MB，一共需要101次这样的比较。

• 堆排序
  堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  小顶堆（min-heap）：每个结点的值均不大于其左右孩子结点的值，则堆顶元素即为整个堆的最小值。
  大顶堆（max-heap）：每个结点的值均大于其左右孩子结点的值，则堆顶元素即为整个堆的最大值。

  JDK中PriorityQueue实现了数据结构堆，PriorityQueue是一个基于优先级的无界优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法，通过指定comparator字段来表示小顶堆或大顶堆，默认为null，表示自然序（natural ordering）。

小顶堆解决Top K问题的思路：小顶堆维护当前扫描到的前10000个数，其后每一次的扫描到的元素，若大于堆顶，则入堆，然后删除堆顶；依此往复，直至扫描完所有元素

2.2 小顶堆实现

public int findKthLargest(int[] nums, int k) {
  PriorityQueue<Integer> minQueue = new PriorityQueue<>(k);
  for (int num : nums) {
    if (minQueue.size() < k || num > minQueue.peek())
      minQueue.offer(num);
    if (minQueue.size() > k)
      minQueue.poll();
  }
//这时候队列中就是topk，并且有序，minQueue.peek()就是第k大数
  return minQueue.peek();

参考：
1、https://github.com/xbox1994/Java-Interview/blob/master/MD/%E7%AE%97%E6%B3%95-%E6%95%B0%E7%BB%84-%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-%E7%AC%ACk%E5%A4%A7%E4%B8%AA%E6%95%B0.md
2、https://www.cnblogs.com/du001011/p/11167603.html
3、https://blog.csdn.net/djrm11/article/details/87924616
4、https://blog.csdn.net/qq_36186690/article/details/82505569