アルゴリズムの検索---高速選択アルゴリズム

高速選択アルゴリズムは、略O(N)の時間内に配列中のk番目に大きいかk番目に小さいかを選択できるアルゴリズムである.その基本構想は高速並べ替えアルゴリズムと類似しており、分治の思想でもある.K番目の大きい数、またはk番目の小さい数を見つけるのに使用できます.
1 Partitionアルゴリズムを実行する(その速い列の中で区間内のすべての数を小さい部分と大きい部分に分ける過程である)2 k番目に大きい数が小さい部分にあるか大きい部分にあるかを判断する3は、区間が十分に小さいまで再帰し、結果を返す

package selectTest;

import javax.print.attribute.standard.Media;

public class qucikSelect {

    private static int qucikselect(int[] a, int from, int to, int k) {
        if(k>a.length) return -1;
        int i = from, j = to, m = (i + j) / 2;
        while (i <= j) {
            while (a[i] < a[m])
                i++;
            while (a[j] > a[m])
                j--;
            if (i <= j) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
                i++;
                j--;
            }
        }
        if (from < j && k <= j)
            return qucikselect(a, from, j, k);
        if (i < to && k <= i)
            return qucikselect(a, i, to, k);
        return a[k-1];
    }

    public static void main(String[] args) {
        int[] test = { 1,2,3,5,5,4,6,7,8,9};
        System.out.println(qucikselect(test, 0,test.length-1,1));
        System.out.println();
        for(int i=0;i<test.length;i++){
            System.out.print(test[i]+"\t");
        }

    }
}

バージョン2

package selectTest;

import javax.print.attribute.standard.Media;

public class qucikSelect {

    private static int qucikselect(int[] s, int l, int r, int k) {
        if (k > s.length)
            return -1;
        if (l < r) {
            int i = l, j = r, x = s[l]; // x   

            while (i < j) {
                while (i < j && s[j] >= x)
                    //           x  
                    j--;
                if (i < j)
                    s[i++] = s[j];

                while (i < j && s[i] < x)
                    //             x  
                    i++;
                if (i < j)
                    s[j--] = s[i];
            }
            s[i] = x; //      s[i]
            if (i < k-1)
                return qucikselect(s, i + 1, r, k);
            else if (i > k-1) {
                return qucikselect(s, l, i - 1, k);
            } else {
                return s[i];
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] test = { 1,4,3,7};
        System.out.println(qucikselect(test, 0, test.length - 1, 3));
        System.out.println();
        for (int i = 0; i < test.length; i++) {
            System.out.print(test[i] + "\t");
        }

    }
}