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

问题

找出给定数组的第x大的数

code

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;
    }

复杂度

$O(n)$

证明比较繁琐,参见<<算法导论>> ,直观上根据算法可知,只是不断的递归找该索引在的高区或者低区,没有排序,只是做了线性的选择,复杂度应为$O(n)$