无序数组中找到第 K 大的元素（快排改进版）

思路：我们利用快排分区的思想来解答这个问题，我们以数组最后一个元素记为 pivot, 将数组分为三个部分，a[0..q-1]， a[q],a[q+1...r]，然后我们比较 q+1 是否等于 k , 如果相等，我们返回 a[q]，q+1 > k，我们在 a[0,q-1] 中递归寻找。
时间复杂度分析：第一次分区，我们查找了 n 个元素，第二次我们查找了 n/2 个元素，依次类推，最后区间缩小到 1，复杂度为 n+n/2 + n/4 + ....+1 为 O(2n-1) 即 O(n)。

import java.util.*;

public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return sortUseQuickSort_C(a,0,n-1,K);
    }
     private int sortUseQuickSort_C(int[] a, int p, int r, int k) {
         int q = partition(a,p,r,k);
        if(q+1 == k ) return a[q]; 
        else if(q+1 > k) return sortUseQuickSort_C(a,p,q-1,k);
        else return sortUseQuickSort_C(a,q+1,r,k);
    }

    private int partition(int[] a, int p, int r, int k) {
        int pivot = a[r];
        int i = p;
        int j = p;
        for(; j< r; j++) {
            if(a[j] > pivot) {
                if(i ==j) {
                    i++;
                } else {
                    swap(a,i,j);
                    i++;
                }
            }
        }
        swap(a,i,r);

        return i;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}