public static int select(int[] arr, int k) {
        int n = arr.length;
        int l = 0;
        int ir = n - 1;

        int a;
        int i, j, mid;
        for (;;) {
            if (ir <= l + 1) {
                if (ir == l + 1 && arr[ir] < arr[l]) {
                    SortUtils.swap(arr, l, ir);
                }
                return arr[k];
            } else {
                mid = (l + ir) >> 1;
                SortUtils.swap(arr, mid, l + 1);
                if (arr[l] > arr[ir]) {
                    SortUtils.swap(arr, l, ir);
                }
                if (arr[l + 1] > arr[ir]) {
                    SortUtils.swap(arr, l + 1, ir);
                }
                if (arr[l] > arr[l + 1]) {
                    SortUtils.swap(arr, l, l + 1);
                }
                i = l + 1;
                j = ir;
                a = arr[l + 1];
                for (;;) {
                    do {
                        i++;
                    } while (arr[i] < a);
                    do {
                        j--;
                    } while (arr[j] > a);
                    if (j < i) {
                        break;
                    }
                    SortUtils.swap(arr, i, j);
                }
                arr[l + 1] = arr[j];
                arr[j] = a;
                if (j >= k) {
                    ir = j - 1;
                }
                if (j <= k) {
                    l = i;
                }
            }
        }
    }
public static int select ( int [ ] arr , int k ) { int n = arr . length ; int l = 0 ; int ir = n - 1 ; int a ; int i , j , mid ; for ( ; ; ) { if ( ir <= l + 1 ) { if ( ir == l + 1 && arr [ ir ] < arr [ l ] ) { SortUtils . swap ( arr , l , ir ) ; } return arr [ k ] ; } else { mid = ( l + ir ) > > 1 ; SortUtils . swap ( arr , mid , l + 1 ) ; if ( arr [ l ] > arr [ ir ] ) { SortUtils . swap ( arr , l , ir ) ; } if ( arr [ l + 1 ] > arr [ ir ] ) { SortUtils . swap ( arr , l + 1 , ir ) ; } if ( arr [ l ] > arr [ l + 1 ] ) { SortUtils . swap ( arr , l , l + 1 ) ; } i = l + 1 ; j = ir ; a = arr [ l + 1 ] ; for ( ; ; ) { do { i ++ ; } while ( arr [ i ] < a ) ; do { j -- ; } while ( arr [ j ] > a ) ; if ( j < i ) { break ; } SortUtils . swap ( arr , i , j ) ; } arr [ l + 1 ] = arr [ j ] ; arr [ j ] = a ; if ( j >= k ) { ir = j - 1 ; } if ( j <= k ) { l = i ; } } } }
Given k in [0, n-1], returns an array value from arr such that k array
values are less than or equal to the one returned. The input array will
be rearranged to have this value in location arr[k], with all smaller
elements moved to arr[0, k-1] (in arbitrary order) and all larger elements
in arr[k+1, n-1] (also in arbitrary order).