从百万数据中找到第K大的数并且时间复杂度为O(N)

假设数组为array，求第K大的元素。

注意：因为快排排序后，数组是由小到大的，所以第K大的元素为倒数第十个即 array[array.length-K+1]；

所以我们要令k =array.length-K+1

思路：利用快排的分治思想，先对数组进行一趟快排，将数组分为三个区，（0，par），（par），（par+1，array.length-1）。判断k与par的大小，如果par +1<k,那么下次对（par+1，array.length-1）这一部分进行快排，如果par+1>k,则对（0，par-1）进行快排。直到par == k，那么第K大的数就是array[par].

为什么说时间复杂度为O(N),第一次分区查找，我们需要对n个元素进行分区，第二次分区查找，需要对n/2个元素进行分区。依次类推，直到区间缩小为1.那么总时间复杂度为：n+n/2+n/4+n/8+...+1，等比数列求和，和为2n-1。所以时间复杂度为O(N).

代码实现如下：

import java.util.Random;

public class FindK {
    public static void main(String[] args) {
        Random r = new Random();
        int K = 10;//第K大的数
        int[] array = new int[200];
        for(int i =0 ;i<array.length;i++){
            array[i] = r.nextInt(4000);
        }
        //快排排出来是由小到大的，所以第K大的数，也就是倒数第十个数，
        //即k=array.length-K+1
        int k = array.length-K+1;
        int par = parton(array,0,array.length-1);
        while(par + 1 != k){
            if(par+1<k){
                par = parton(array,par+1,array.length-1);
            }else if(par+1>k) {
                par = parton(array,0,par-1);
            }
        }
        System.out.println(array[par]);

    }

    public static int parton(int[] array,int l,int h){
        if(l<h){
            int tmp = array[l];
            while(l<h){
                while(l<h && array[h]>=tmp){
                    h--;
                }
                if(l<h){
                    array[l++] = array[h];
                }
                while(l<h && array[l]<=tmp){
                    l++;
                }

                if(l<h){
                    array[h--] = array[l];
                }
            }

            array[l] = tmp;
            return l;
        }
        return -1;
    }
}