Randomize select algorithmランダム選択アルゴリズム

1つのシーケンスからk番目の数を選択するアルゴリズム導論を学習する前に、この配列をソートし、ソート結果に従ってk番目の数値を返すのが最も一般的な考えだと思います.並べ替え方法を用いると,時間的複雑さは少なくともO(nlgn)であるに違いない.
問題は,シーケンスからk番目に大きい数を選択して並べ替える必要が全くなく,分治法の考え方でこの問題を解決できることである.Randomize selectアルゴリズムの期待時間の複雑さはO(n)に達することができ,これがこのアルゴリズムの魅力である.具体的なアルゴリズム分析は『アルゴリズム導論』という本で見ることができる.
ダミーコードを貼り付けます.

RANDOMIZED-SELECT(A, p, r, i)

1  if p = r

2      then return A[p]

3  q ← RANDOMIZED-PARTITION(A, p, r)

4  k ← q - p + 1

5  if i = k          ▹ the pivot value is the answer

6      then return A[q]

7  elseif i < k

8      then return RANDOMIZED-SELECT(A, p, q - 1, i)

9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

このアルゴリズムの思想は実はquik-sortと少し似ていて、分治法の思想を採用して解決します.まず1つのメタpirvot:qを選択し、シーケンス中の要素を2つの集合Q,Wに分け、Qの中の要素はすべてメタpirvotより小さく、Wの中の要素はpirvotより大きい.そして、このプロセスを再帰的に呼び出すと、私たちが望んでいるi番目の要素を得ることができます.ここの区分には3つの状況があります.
1:マスターの選択はちょうどi番目の大きい要素で、それではこの要素を返します
2:Qの中の元素の個数k=(q-p+1)はiより大きく、i番目の大きい元素がQという集合の中にあることを表し、この過程を続けてi番目の小さい元素を探す(step 7-8)
3:Qの中の元素の個数k=(q-p+1)はiより小さくて、すでにk個の小さい元素を見つけたことを代表して、それではi番目の小さい元素はきっとWのこの集合の中で、W集合の中で(i-k)番目の小さい元素を探すだけでいいです
このアルゴリズムのjava実装を次に示します.

/**

 *           ，         。

 * @author    ：http://blog.csdn.net/zy825316/article/details/19486167

 

 */

public class randomizedSelect {





    /**

     * @param args

     */

    public static void main(String[] args) {

         int a[]={2,5,3,0,2,3,0,3};

        

         int result=randomizedSelect(a,0,a.length-1,3);//       

         System.out.print("
"+result);

    }

    

    private static int partition(int[] a, int p, int r) {

        int x=a[r];

        int i=p-1;

        for(int j=p;j<r;j++){

            if(a[j]<=x){

                i=i+1;

                swap(a, i, j);

            }

        }

        swap(a, i+1, r);

        return i+1;

    }

    

    private static int randomizedPartition(int[] a,int p,int r){

        java.util.Random random = new java.util.Random();

        int i=Math.abs(random.nextInt() % (r-p+1)+p);//           

        swap(a,i,r);

        return partition(a,p,r);

    }

    

    

    /**

     * 

     * @param a   

     * @param p         

     * @param r          

     * @param i          

     * @return

     */

    private static int randomizedSelect(int[] a,int p,int r,int i){

        if(p==r){

            return a[p];//               

        }

        int q=randomizedPartition(a,p,r);

        int k=q-p+1;//                  

        if(i==k){

            return a[q];

        }else if(i<k){

            return randomizedSelect(a,p,q-1,i);

        }else{

            return randomizedSelect(a,q+1,r,i-k);

        }

        

    }

    

    private static void swap(int[] a, int i, int j) {

        int temp=a[i];

        a[i]=a[j];

        a[j]=temp;

    }





}