题解 | #寻找第K大#

本文仅用于记录本人笔记
又是一道快排模板题，爷喜欢！~
还是那个从牛客题解里看到的一位牛人的快排题思路：快排思想就是每一轮的结果必须是本轮中枢元的左边都比中枢元小，右边都比中枢元大，然后分治即可。
关于中枢元的选取和交换策略，衍生出了众多不同的快排代码写法，这里的解法非常简单，是我见过最简单好记的一种：也就是取第一个位置作为中枢元，然后从它后一位开始到整个本轮数组范围遍历，只要比中枢元小的都跟中枢元后++i位交换，这个i是中枢元这一位置开始，代表中枢元后面有i个比中枢元小的数。遍历完最后交换下i和中枢元的位子即可达到本轮目的（左边都小，右边都大）。

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        quickSort(a,0,a.length-1);
        return a[n - K];
    }
    public void quickSort(int[] a,int begin,int end){
      if(begin < end){
        int theSelectedNum = begin;
        int thSelectedValue = a[begin];
        for(int i = begin + 1;i <= end;i++){
            if(a[i] < thSelectedValue){
                swap(a,++theSelectedNum,i);
            }
        }
        a[begin] =  a[theSelectedNum];
        a[theSelectedNum] = thSelectedValue;
        quickSort(a,begin,theSelectedNum-1);
        quickSort(a,theSelectedNum+1,end);
       }

    }
    public void swap(int[] a,int left,int right){
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }
}