题解 | #寻找第K大#

算法思路

要找数组中第K大的数，很简单的就是将数组从大到小进行排序，然后输出数组第K个数即可；排序的话我们选择快速排序，简单高效，而且因为是原地排序空间复杂度也低；不同于#排序#中从小到大排序，只要修改partition()方法交换判定条件，即可实现从大到小排序；

算法实现

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

    private void quickSort(int[] A, int L, int R) {
        if (L < R) {
            int p = partition(A, L, R);
            quickSort(A, L, p - 1);
            quickSort(A, p + 1, R);
        }
    }

    private int partition(int[] A, int L, int R) {
        int pivot = A[R];
        int i = L - 1;
        for (int j = L; j < R; j++) {
            if (A[j] >= pivot) {
                swap(A, ++i, j);
            }
        }
        swap(A, i + 1, R);
        return i + 1;
    }

    private void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}