Javaは線形時間の選択アルゴリズムを期待する

配列中の最大値を選択するアルゴリズムの時間的複雑度はO(n−1)である.
配列中の最小値を選択するアルゴリズムの時間複雑度はO(n−1)である.
しかし、最大値と最小値を同時に選択する時間的複雑度はO(3 n/2)である.
配列中にi番目の小さい得数アルゴリズムを選択する所望の時間は線形である
アルゴリズムは高速ソートの核心思想を採用する

  public int  select(int[] array, int sta, int end,int index){// index     index    
        if(sta == end)
            return array[sta];

        int q = partition(array,sta,end) ;
        int k = q - sta + 1;
        if(k == index)
            return array[q];
        else if(index < k)
            return select(array, sta, q-1, index);
        else
            return select(array, q+1, end, index - k);
    }

partition関数、参照 
Javaソートの高速ソート記事;
http://blog.csdn.net/alvintech14/article/details/38403753