毎日少しのアルゴリズムを勉強します.

線形検索アルゴリズム
定義
BFRTTアルゴリズムで解決された問題は、あるn個の要素のシーケンスからk番目の大きい(k番目の小さい)要素を選び、巧みな分析によって、BFRTTは最悪の場合でも線形時間の複雑さを保証することができる.このアルゴリズムの思想は高速秩序化思想と似ているが、もちろん、アルゴリズムが最悪の場合にもo(n)の時間複雑さを達成できるように、5ビットのアルゴリズムの著者らは巧みな処理を行った.
ステップ
1.n個の要素を5つのグループに分けて、n/5(上界)グループに分けます.
2. 各グループの中央値を取り出し、並べ替えを挿入するなど、任意の並べ替え方法を選択します.
3. 再帰的な呼び出しセレクションアルゴリズムは、前のステップのすべての中央値の中央値を検索し、xに設定し、偶数の中のビット数の場合は、中間の小さな1つを選択するように設定される.
4. 配列をxで分割し、x以下の個数をkとし、xより大きい個数をn-kとする.
5. i=kなら、xに戻るikの場合は、xより大きい要素の中から、i番目の小さい要素を再帰的に検索する.
終了条件:n=1の場合は、i小要素を返します.
時間の複雑さ
O(n)
コード

public class BFPRT {
	public int find(int[] a, int j) {
		System.out.println("================================");
		System.out.println("       ： ");
		print(a);
		System.out.println("    " + j + "   ");
		if (a.length / 5 == 1) {
			return a[a.length - 1];
		}

		int x = getCenterForArray(a);

		// 4.  x     ，     x    k，  x     n-k。
		List left = new ArrayList();
		List right = new ArrayList();

		for (int i = 0; i < a.length; i++) {
			if (a[i] <= x) {
				left.add(a[i]);
			} else {
				right.add(a[i]);
			}
		}
		// 5.  i==k，  x； ik，   x         i-k     。
		int K = left.size();
		if (j == K) {
			return x;
		} else if (j < K) {
			int[] leftArray = new int[left.size()];
			for (int i = 0; i < left.size(); i++) {
				leftArray[i] = left.get(i);
			}
			return find(leftArray, j);
		} else {
			int[] rightArray = new int[right.size()];
			for (int i = 0; i < right.size(); i++) {
				rightArray[i] = right.get(i);
			}
			return find(rightArray, j - K);
		}
	}

	//           
	private int getCenterForArray(int[] a) {
		// 1. n    5   ，  n/5(  ) ，            n%5，      n/5。
		int length = a.length;
		int num = length / 5;
		int[] centers = new int[num];
		for (int i = 0; i < num; i++) {
			//          
			int center = getCenterPerArray(a, 5 * i, 5 * (i + 1) - 1);
			centers[i] = center;
			System.out.println("        : " + center);
		}
		System.out.println("       ： ");
		print(centers);
		// 3.       selection                  ，  x，                     。
		new Selectionsort().sort(centers);
		System.out.println("              ： ");
		print(centers);
		int x = 0;

		if (centers.length % 2 == 0) {
			//       
			x = min(centers[centers.length / 2 - 1],
					centers[centers.length / 2]);
		} else {
			x = centers[centers.length / 2];
		}
		System.out.println("   x   ： " + x);

		return x;
	}

	private int min(int a, int b) {
		if (a >= b) {
			return b;
		} else {
			return a;
		}
	}

	//             
	private int getCenterPerArray(int[] a, int start, int end) {
		// 2.         ，             ，      ，          5 ，                。
		int[] b = new int[end - start + 1];
		int index = 0;
		for (int i = start; i <= end; i++) {
			b[index++] = a[i];
		}
		System.out.println("       ： ");
		print(b);
		new Insertsort().sort(b);
		return b[b.length / 2];
	}

	public static void main(String[] args) {
		//      7   

		int[] datas = { 4, 1, 2, 56, 24, 5, 6, 97, 8, 0, 4, 8, 6, 2, 3, 6, 1,
				9, 3, 4, 6, 2 };
		int index = 8;
		int findX = new BFPRT().find(datas, index);
		datas = new QuickSort().sort(datas);
		print(datas);
		System.out.println(" " + index + "     ： " + findX);
	}

	public static void print(int[] datas) {
		for (int i = 0; i < datas.length; i++) {
			System.out.print(datas[i] + " ");
		}
		System.out.println("");
	}

}

出力

================================
       ： 
4 1 2 56 24 5 6 97 8 0 4 8 6 2 3 6 1 9 3 4 6 2 
    8   
       ： 
4 1 2 56 24 
        : 4
       ： 
5 6 97 8 0 
        : 6
       ： 
4 8 6 2 3 
        : 4
       ： 
6 1 9 3 4 
        : 4
       ： 
4 6 4 4 
              ： 
4 4 4 6 
   x   ： 4
================================
       ： 
4 1 2 0 4 2 3 1 3 4 2 
    8   
       ： 
4 1 2 0 4 
        : 2
       ： 
2 3 1 3 4 
        : 3
       ： 
2 3 
              ： 
2 3 
   x   ： 2
================================
       ： 
4 4 3 3 4 
    2   
0 1 1 2 2 2 3 3 4 4 4 5 6 6 6 6 8 8 9 24 56 97 
 8     ： 4