[牛客アルゴリズムシリーズ]BFPRTアルゴリズム

BFPRTアルゴリズムO(n)はk番目の小さい数を解決する
通常、高速ソートを簡単に行い、k番目の位置の数字を得ることができます.高速並べ替えは不安定な並べ替えであることが知られており,その並べ替え過程の簡単な理解は主に2つの概念Partion,pivot(基準数)である.
迅速なソートの手順は次のとおりです.

まずシーケンスから1つの数を基準数

として選択する.

この数より大きい数をすべてその右側に置き、それ以下の数をすべてその左

に置く.
1回のクイックソートはPartionとも呼ばれ、シーケンスを2つの部分に分割し、一部はベース準数より小さく、もう一部はベース準数より大きく、それから分治過程を行います.1回のPartionごとに均一な区分が保証されるとは限らないので、最悪の場合の時間複雑度は常にO(nlogn)であることは保証されません.
BFPRTアルゴリズム
BFTRアルゴリズムでは、単にクイックソートPartionのpivot値の選択を変更しただけで、クイックソートでは、常に最初の要素または最後の要素をpivotとして選択しますが、BFTRアルゴリズムでは、pivotとして5分中位数の中位数を選択するたびに、分割を合理化し、最悪の事態を回避することを目的としています.アルゴリズムの手順は次のとおりです.
(1)入力配列のn個の要素をn/5個のグループに分け,各グループに5個の要素があり,残りのn%5個の要素からなるグループは最大1個のみである.(2)n/5個のグループの各グループの中位数を探し、まず各グループの要素を挿入してソートし、ソートしたシーケンスから中位数を選択する.(3)(2)で見つかったn/5中位数について、(1)と(2)を再帰的に行い、このn/5要素の中位数が1つしか残っていないまで、中位数を見つけて対応する下付きpを見つける.(4)パーティション分割プロセスを行い,パーティション分割におけるpivot要素の下にpと表記する.(5)高低域判定を行えばよい.
本アルゴリズムの最悪時間複雑度はO(n)であり,BFTRアルゴリズムにより配列をK番目に小さい(大きい)要素で2つの部分に分割することに注目すべきであるが,この高低2つの部分は必ずしも秩序化されているとは限らず,通常は順序を求める必要はなく,前Kが大きいまたは前Kが小さいだけを求める必要がある.
コード#コード#

import java.util.*;

public class BFPRT {
    public final int MAXN = 100000;

    public static void swap(int [] x , int i , int j){
        int tmp = x[i];
        x[i] = x[j]; x[j] = tmp;
    }

    public static void sort(int [] x , int l , int r){
        for(int i=l ; i<=r ; i++){
            for(int j=i+1 ; j<=r ; j++){
                if(x[j]<x[i]) swap(x , i , j);  //           ，    ，      
            }
        }
    }

    public int findMedian(int []x , int l  , int r){
        int i , index;
        for(i=l , index=0 ; i+4<=r ; i+=5 , index++){
            sort(x , i , i+4);
            swap(x , l+index , i+2);
        }
        //  5         
        if(i<=r){
            sort(x , i , r);
            swap(x , l+index , i+(r-i+1)/2);
            index++;
        }
        if(index == 1) return x[l+index];
        else return findMedian(x , l , l+index-1);
    }
    //  x   [l,r]    k   
    public int findKthMin(int [] x , int l , int r , int k){
        int median = findMedian(x , l , r);
        //          ，    pivot        x[l]，        ，      
        //    ，      x[l] l       ，
        //            j          i （   i=l)，  i       ，
        //                  j ，  i>=j
        int mediemVal = x[l];
        int i=l , j=r;
        while(i<j){
            while(i<j && x[j]>mediemVal) j--;
            if(i<j) x[i] = x[j];
            while(i<j && x[i]<mediemVal) i++;
            if(i<j) x[j] = x[i];
        }
        x[i] = mediemVal;
        if(i-l+1 == k) return x[i];
        else if(i-l+1 > k) return findKthMin(x , l , i-1 , k);
        else return findKthMin(x , i+1 , r , k-(i-l+1));
    }

    public static void main(String [] args){

        int []x = {2,3,6,5,7,9,4};
        BFPRT sol = new BFPRT();
        //int val = sol.findMidiem(x , 0 , 6);
        int val = sol.findKthMin(x , 0 , x.length-1 , 3);
        System.out.println(val);
    }
}