题解 | #寻找第K大#

import java.util.*;


//时间复杂度 O(nlogn)，快速排序 先排序再找

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {       
        //快速排序
        quickSort(a,0,n-1);
        //第K大的，相当于倒数第K个
        return a[n-K];
    }

    void quickSort(int[] a, int start, int end) {
        //递归进来要满足的条件
        if (start < end) {
            //左右指针
            int l = start;
            int r = end;

            //申明参照对象，任意都可以，这里初始选最左边元素
            int target = a[l];
            //参照对象初始最左边，从最右侧指针开始

            //一直比，知道两个指针相遇
            while (l < r) {
                //一直比参照大，所以右侧指针 --
                while (l < r && a[r] >= target) {
                    r--;
                }
                //遇到比参照小的,把值放到左侧
                if (l < r) {
                    a[l] = a[r];
                    l++; //下次从左侧开始，l++
                }
                while (l < r && a[l] <= target) {
                    l++;
                }
                //遇到比参照小的,把值放到左侧
                if (l < r) {
                    a[r] = a[l];
                    r--; //下次从左侧开始，l++
                }
            }

            //指针相遇，把target值放回相遇点
            a[l] = target;

            //从相遇地方左右两侧分别开始递归
            quickSort(a, start, l-1);
            quickSort(a, l+1, end);

        }
    }
}