题解 | #寻找第K大#

1.使用快速排序的分区方法，创造出一个数num， 使得num左边的数都小于等于num，num右边的数都大于等于num，获取到num在arr中的索引值mid
2.题意为求第k大的数，即求升序排序之后第n - k个数，所以将k赋值为n-k（如果分区方法是倒序排序的话，这一步可不进行）。
3.如果第一步获取到的索引值mid小于第二步中的k，那就将数组的左边界变为mid+1；
如果第一步获取到的索引值mid大于第二步中的k，那就将数组的右边界变为mid-1；
一直循环第一步和第三步，直到当mid等于k的时候，返回arr[mid]

代码如下

public int findKth(int[] a, int n, int k) {
       int left = 0;
       int right = n - 1;
       k = n - k;
       while (left <= right) {
           int mid = partition(a, left, right);
           if (k > mid) {
               left = mid + 1;
           }else if (k < mid) {
               right = mid - 1;
           }else {
               return a[mid];
           }
       }
       return -1;
   }


   private int partition(int[] arr, int left, int right) {
       // 定义主元
       // 小的指针
       int sp = left;
       // 大的指针
       int bigger = right;
       while (sp <= bigger) {
           if (arr[sp] <= arr[left]) {
               sp++;
           } else {
               swap(arr, sp, bigger);
               bigger--;
           }
       }
       swap(arr, left, bigger);
       return bigger;
   }

   public void swap(int[] arr, int a, int b) {
       int temp = arr[a];
       arr[a] = arr[b];
       arr[b] = temp;
   }