この記事では、分割および征服アルゴリズムに基づいてJavaによって実装された線形時間選択操作について説明します。次のように、参照のために共有してください。
線形時間選択の問題： n要素と整数k、1≤k≤nが与えられた場合、これらのn要素の最小要素を見つける必要があります（ここで与えられた線形セットは無秩序です）。
ランダムに分割された線形選択
線形時間選択ランダム分割法は、ランダム化されたクイックソートアルゴリズムの設計を模倣できます。基本的なアイデアは、入力配列を再帰的に分割することです。クイックソートとは異なり、分割されたサブアレイの1つを再帰的に処理するだけです。
プログラムの説明：ランダム関数を使用してディビジョンベンチマークを生成し、配列a [p：r]を2つのサブアレイA [p：i]と[i+1：r]に分割します。これにより、[p：i]の各要素が[i+1：r]の各要素よりも大きくありません。次に、「j = i-p+1」は、a [p：i]の要素jの数を計算します。 k <= jの場合、[p：r]のk番目の最小要素はサブアレイa [p：i]にあり、k> jの場合、k番目の小さな要素はサブアレイa [i+1：r]にあります。注：サブアレイA [P：I]の要素はすべて発見されるk番目の小さな要素よりも小さいことが知られているため、[p：r]のk番目の小さな要素は[i+1：r]のk番目の小さな要素です。
たとえば、最悪の場合：最小の要素が常に見つかった場合、常に最大の要素で分割されます。これはO（n^2）の時間の複雑さです。ただし、平均時間の複雑さはnに直線的に関連しています。これはo（n）です
パッケージMath; Import Java.util.scanner; Import Java.util.random; public class randomSelect {public static void swap（int x、int y）{int temp = x; x = y; y =温度; } public int random（int x、int y）{random = new Random（）; int num = random.nextint（y）％（y -x + 1） + x; numを返します。 } public intパーティション（int [] list、int low、int high）{int tmp = list [low]; //配列の最初のものは中心軸ですwhile（low <high）{while（low <high && list [high]> tmp）{high--; } list [low] = list [high]; //中心軸よりも小さい記録はローエンドに移動しますが、low <high && list [low] <tmp）{low ++; } list [high] = list [low]; //中心軸よりも大きい記録は、ハイエンドに移動されます}リスト[low] = tmp; //中心軸よりも大きいレコードは低く戻ります。 //中心軸の位置に戻る} public int randomizedPartition（int [] arrays、int left、int右）{int i = random（左、右）;スワップ（配列[i]、配列[左]）;パーティションを返します（配列、左、右）; } public int randomizedSelect（int [] arrays、int left、int right、int k）{if（左==右）{return arrays [左]; } int i = randomizedPartition（配列、左、右）; int j = i-左 + 1; if（k <= j）{return randomizedSelect（arrays、left、i、k）; } else {return randomizedselect（arrays、i+1、右、kj）; }} public static void main（string args []）{system.out.println（ "wulin.comテスト結果："）; int [] a = {7,5,3,4,8,6,9,1,2}; for（int i = 0; i <9; i ++）{system.out.print（a [i]+""）; } system.out.println（）; randomSelect r = new RandomSelect（）; system.out.println（「配列でクエリする最小要素は何ですか？」）; @suppresswarnings（ "Resource"）スキャナーSC = new Scanner（System.in）; int m = sc.nextint（）; int n = R.RandomizedSelect（a、0,8、m）; System.out.println（ "The" the "the" the "in this array" + m + "最小の要素は" + n）; }}実行結果：
Javaアルゴリズムの詳細については、このサイトに興味のある読者は、「Javaデータ構造とアルゴリズムのチュートリアル」、「Java操作DOMノードのヒントの要約」、「Javaファイルの要約およびディレクトリ操作のヒント」、「Java Cache操作のヒントの要約」というトピックを見ることができます。
この記事がみんなのJavaプログラミングに役立つことを願っています。