0

私はphpでバブルソート戦略について勉強しています。コードはこちらです。メインループでは、2つの条件が真である必要があるため、ループが実行されます。変数は、ループを実行したくないためであることを理解しています配列がすでにソートされていても最大反復ですが、最大反復に達したかどうかを確認する必要がある理由がわかりませんでしたか? 変数をチェックできないのはなぜですか (私の仮定では、変数に何らかの問題が発生する可能性があり、永遠のループは必要ありません)。いずれにせよ、メインループで変数だけをチェックする必要がない理由を教えていただければ、とても感謝しています。ありがとうございました。良い一日を。

function sort(array &$vec)
    {
        $sorted = false;
        $size = sizeof($vec);
        for($i=0; $i<=$size-2 && !$sorted; $i++)
        {
            $maybeSorted = true;
            $from = 0;
            $till = $size-1-$i;
            for($j=$from; $j<$till; $j++)
            {
                if($vec[$j]>$vec[$j+1])
                {
                    $maybeSorted = false;
                    $temp = $vec[$j];
                    $vec[$j] = $vec[$j+1];
                    $vec[$j+1] = $temp;
                }
            }
            if($maybeSorted)
            {
                $sorted = true;
            }
        }
    }
4

1 に答える 1

0

このウィキペディアのリンクをチェックアウトすると、疑似コードでアルゴリズムを見つけることができます。各ステップを理解し、好みの言語で新しい実装を開始してください。これは sth を学ぶ最良の方法です。新着！

バブル ソートは、各ラウンドで要素を交換し、最後のラウンドで何も交換されなくなるまでこれを繰り返します。

更新優れたバブルソートアルゴリズムの例:

function sort(array &$vec) {
  $n = sizeof($vec);

  do {
    $newn = 1;
    for ($i = 0; $i < ($n - 1); $i++) {
      if ($vec[$i] > $vec[$i + 1]) {
        $tmp         = $vec[$i];
        $vec[$i]     = $vec[$i + 1];
        $vec[$i + 1] = $tmp;
        $newn        = $i + 1;
      }
    }
    $n = $newn;
  } while ($n > 1);
}
  1. 配列内の要素の数を取得します (現在、何もソートされていないと予想されます)
  2. $nソートされていない要素がある間はループするので、$n > 1
  3. ループではfor、要素を調べて、それらを交換する必要があるかどうかを確認します
  4. $nスワップする要素がなくなるまでこれを行います。> 1

例：

| 55 |  7 | 78 | 12 | 42 | 1. run
|  7 | 55 | 78 | 12 | 42 |
|  7 | 55 | 12 | 78 | 42 |
|  7 | 55 | 12 | 42 | 78 | last comparison
|  7 | 55 | 12 | 42 | 78 | 2. run
|  7 | 12 | 55 | 42 | 78 |
|  7 | 12 | 42 | 55 | 78 | last comparison (we now 78 is sorted!)
|  7 | 12 | 42 | 55 | 78 | 3. run
|  7 | 12 | 42 | 55 | 78 | sorted! (nothing was swapped)

（テストされていませんが、動作するはずです）これがお役に立てば幸いです。

于 2012-06-13T14:05:38.653 に答える