ブルートフォースを使用して選択ソートの問題を解決する

ブルート フォース手法は、問題を解決するためのシンプルかつ直接的な方法であり、多くの場合、問題の説明と関係する概念の定義に直接基づいています。

選択の並べ替えのアイデア:

選択による並べ替えの開始時に、リスト全体をスキャンして最小の要素を見つけ、それを最初の要素と交換し、順序付きリストの最後の位置に最小の要素を置きます。次に、2 番目の要素からリストをスキャンし、最後の (n-1) 個の要素の最小値を見つけて、それを 2 番目の要素と交換し、2 番目に小さい要素をリストの最後の位置に置きます。一般に、i 回目にリストをスキャンするとき (i の値は 0 から n-2 の範囲です)、アルゴリズムは最後の (n-i) 要素の中から最小の要素を探し、それを Ai と交換します。 ( n-1) が経過すると、リストがソートされます。

次は私のコード実装です: C

リーリー

アルゴリズムの分析:

入力のサイズは要素数 n によって決まります。基本的な操作はキー値の比較 Arr[minn] > Arr[j] です。この比較が実行される回数は、配列のサイズにのみ依存します。

C(n)=∑[i=0,i=N-2] ∑[j=i 1,j=N-1]=∑[i=0,i=N-2] ((N- 1)-(i 1) 1))=∑[i=0,i=N-2](N-i-1)=(n-1)*n/2

つまり、任意の入力に対して、選択ソートは時間計算量 Θ(n2) のアルゴリズムです。キー交換の数は Θ(n) です。 これにより、選択ソートのパフォーマンスが向上します。

以上がブルートフォースを使用して選択ソートの問題を解決するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。