ブルートフォースを使用してバブルソートを解決する

バブル ソートは、ブルート フォース メソッドのもう 1 つの古典的な実施形態です。

アルゴリズムのアイデア: リスト内の隣接する要素を比較し、順序が逆の場合は位置を交換します。何度も繰り返すと、最大の要素が最後にランク付けされます。 2 番目の操作では、2 番目の要素が最後から 2 番目の位置に移動され、比較は n-1 回まで継続され、リスト全体が並べ替えられます。

アルゴリズム分析: 入力のサイズは N によって完全に決定されます。基本的な操作は比較です: Arr[j]>Arr[j 1]、時間計算量 C(n)=Θ(n2).

ただし、鍵交換の回数は特定の入力に依存します。最悪のケースは、必要なソートの逆です。このとき、鍵交換の数 = 鍵の比較の数 = Θ(n2).

しかし、入力状況によっては、リストを比較した後で要素の位置が交換されない場合、リストはすでに整っていて、アルゴリズムを停止できます。具体的な改良版は以下の通りです:

しかし、最悪の場合でも、時間計算量は依然として Θ(n2) です。

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