@@ -0,0 +1,1012 @@
+package problems;%0A%0Apublic class QuickSelect %7B%0A    // Select the Kth smallest number in A, average O(n)%0A    public int select(int%5B%5D A, int K) %7B%0A        if (A == null %7C%7C A.length %3C K)%0A            return -1;%0A%0A        return quickSelect(A, 0, A.length - 1, K);%0A    %7D%0A%0A    public int quickSelect(int%5B%5D A, int l, int r, int K) %7B%0A        int p = l;%0A        for (int i = l; i %3C r; i++) %7B%0A            if (A%5Bi%5D %3C A%5Br%5D)%0A                swap(A, i, p++);%0A        %7D%0A        swap(A, p, r);%0A        if (K == p - l + 1)%0A            return A%5Bp%5D;%0A        else if (K %3C= p - l)%0A            return quickSelect(A, l, p - 1, K);%0A        else%0A            return quickSelect(A, p + 1, r, K - p + l - 1);%0A    %7D%0A%0A    public void swap(int%5B%5D A, int p, int q) %7B%0A        int t = A%5Bp%5D;%0A        A%5Bp%5D = A%5Bq%5D;%0A        A%5Bq%5D = t;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        QuickSelect qs = new QuickSelect();%0A        int%5B%5D A = %7B 3, 2, 5, 7, 5, 3, 9, 0, 1, 8 %7D;%0A        int K = 3;%0A        System.out.println(qs.select(A, K));%0A    %7D%0A%7D%0A

Add Quick Select