算法练习(23) - 快排:顺序统计量

public class _03FindOrderXNumberTest {

    @Test
    public void findOrderXNumber_test() {
        int[]  a = {1,9,16,14,4,7,2,9,10,3};
        int orderXNumber = findOrderXNumber(a, 0, a.length - 1, 9);
        System.out.println(orderXNumber);
    }

    private int findOrderXNumber(int[] a, int p, int q, int x) {
        if(p==q){
            return a[q];
        }
        int r = partition(a,p,q);
         int k = r-p + 1;
         if(k == x){
             return a[r];
         }else if (x>k){
             return findOrderXNumber(a,r+1,q,x-k);
         }else{
             return findOrderXNumber(a,p,r-1,x);
         }
    }

    private int partition(int[] a, int p, int q) {
        int s = a[q];
        int point = p-1;
        for (int i = p; i < q; i++) {
            if(a[i] < s){
                point ++;
                int temp = a[point];
                a[point] = a[i];
                a[i] = temp;
            }
        }
        int temp = a[point+1];
        a[point +1] = a[q];
        a[q] = temp;
        return point +1;
    }