题解 | #寻找第K大#

快排之后，arr[n-k]即为第k大的数。

public int findKth(int[] a, int n, int K) {
        // write code here
        int left = 0, right = a.length - 1;
        quickSort(a, left, right);
        return a[n-K];
    }
    public void quickSort(int[] arr, int left, int right){
        if (left < right){
            int mid = partition(arr, left, right);
            quickSort(arr, left, mid - 1);
            quickSort(arr, mid + 1, right);
        }
    }
    public int partition(int[] arr, int left, int right){
        int pivot = arr[left];
        while (left < right){
            while (left < right && arr[right] >= pivot){
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }