题解 | #寻找第K大#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {
        // write code here

        // 1.先进行排序 - O(NlogN)
        // 手写快排
        // Arrays.sort(a);
        quickSort(a);

        // 2.直接取出第K大元素返回
        return a[n - K];
    }

    // 快速排序主方法
    public void quickSort(int[] a) {
        if (a.length == 0 || a.length == 1) {
            return;
        }
        process(a, 0, a.length - 1);
    }

    // 快速排序递归方法
    public void process(int[] a, int l, int r) {
        // 递归出口
        if (l >= r) {
            return;
        }

        // 先分区，再根据pivort的位置左右递归
        int[] i = partition(a, l, r);
        process(a, l, i[0]);
        process(a, i[1], r);
    }

    // 快速排序分区方法
    public int[] partition (int[] a, int l, int r) {
        int p = a[l];
        int smaller = l - 1;
        int larger = r + 1;
        int i = l;
        while (i < larger) {
            if (a[i] == p) {
                // 当前值等于p，则直接掠过
                i++;
            } else if (a[i] < p) {
                // 发现当前值比p更小，则与smaller的下一个位置交换，smaller自增，表示小于区右扩一位
                // 同时i可以自增，因为从前面交换过来的元素要么等于p，要么是自己交换自己，无需再次比较
                int t = a[i];
                a[i] = a[smaller + 1];
                a[smaller + 1] = t;
                smaller++;
                i++;
            } else {
                // 发现当前值比p更大，则与larger的前一个位置交换，larger自减，表示大于区左扩一位
                // 此时i不能自增，因为从后面交换过来的元素不知道其与p的大小关系，需要再次比较
                int t = a[i];
                a[i] = a[larger - 1];
                a[larger - 1] = t;
                larger--;
            }
        }

        int[] result = {smaller, larger};
        return result;
    }
}