寻找第K大

前言：此类问题就是经典TopK问题
快速排序的详细解析可移至博主另外一篇博文
几种常见排序
下面直接给出题解~
常规快速排序

public int findKth(int[] a, int n, int K) {
        return quickSort(a,0,n-1,K);
    }

    //快速排序
    public int quickSort(int[] a,int left,int right,int k){
        if(left < right){
            int point = partition(a,left,right);
            if (point == k-1)
                return a[k-1];
            else if (point > k-1)
                quickSort(a,left,point-1,k);
            else
                quickSort(a,point+1,right,k);
        }
        return a[k-1];
    }

    //分割
    public int partition(int[] a,int left,int right){
        //基准值
        int base = a[left];

        while(left < right){
            while (left < right && a[right] <= base)
                right--;
            swap(a,left,right);

            while(left < right && a[left] >= base)
                left++;
            swap(a,left,right);
        }
        return left;
    }

    private void swap(int[] a, int left, int right) {
        int tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
    }

基于快排思想
这种方法也是快速排序，跟上面常规的快排有异曲同工之妙。

import java.util.*;

public class Finder {
    public int findKth(int[] a, int n, int K) {
        int left = 0, right = n-1;
        //转换成目标值在数组中的索引
        int target = n-K;
        while(true){
            int index = partition(a,left,right);
            if(index == target)
                return a[index];
            //a[index] 为数组中第index大的值
            else if(index < target)
                left = index+1;
            else 
                right = index-1;
        }
    }

    public int partition(int[] a, int left, int right){
        //以该值为切片
        int pivot = a[left];
        int j = left;
        for(int i = left+1; i <= right; i++){
            //如果切片右边的数小于它，则把小的值放在切片的右邻
            if(a[i] < pivot){
                j++;
                swap(a,j,i);
            }
        }
        //此时上面循环算出来后区间[left+1,j]<pivot && [j+1,right]>pivot
        //下面我们交换left和j的值
        swap(a,left,j); //此时[left,j-1]<pivot && a[j]==pivot && [j+1,right]>pivot

        return j;  //此时因为pivot右边的值都比它大，左边的值都比它小，所以返回它的下标回到主程序判断是否为目标值的下标
    }


    public void swap(int[] a, int j, int i){
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }
}

优化
基准值取随机数

/*添加随机寻找基准值*/
        int random_index = new Random().nextInt(right-left+1)+left;
        swap(a,left,random_index);