PHPバブルソートの使い方を詳しく解説

今回は、PHPバブルソートの使い方と、PHPバブルソートを使用する際の注意点について詳しく説明します。以下は実際のケースです。見てみましょう。

基本的な考え方:

バブルソートは一種の交換ソートです。その基本的な考え方は、隣接するレコードのキーワードをペアごとに比較し、逆順のレコードがなくなるまでそれらを交換するというものです。注文。

最も単純な並べ替えの実装:

さまざまな並べ替え方法を学ぶ前に、よく使用される並べ替え方法を見てみましょう (少なくとも私は...):

//这里使用了类型提示（type hint） array，不熟悉或者不习惯的同学大可去掉，不影响运算结果
function MySort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    for($j = $i + 1;$j < $length;$j ++){
      //将小的关键字放前面
      if($arr[$i] > $arr[$j]){
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
      }
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
MySort($arr);
print_r($arr);

上記のコード 厳密に言えば、これは、「隣接するレコードをペアごとに比較する」というバブル ソートの概念を満たしていないため、標準のバブル ソートではありません。単なる交換ソートです。考え方は次のとおりです。最初のキーワードから始めて、各キーワードとそれに続くすべてのキーワードを比較し、それらを交換して最小値を取得します。しかし、このアルゴリズムは非常に非効率的です。

バブルソートアルゴリズム:

ソート対象のシーケンスを繰り返し訪問し、一度に 2 つの要素を比較し、順序が間違っている場合はそれらを入れ替えます。配列を訪問する作業は、それ以上の交換が必要なくなるまで繰り返されます。これは、配列がソートされたことを意味します。

このアルゴリズムの名前は、並べ替え後に配列内の大きな要素が徐々に配列の後方に「沈み」、小さな要素が徐々に配列の先頭に「浮遊」するという事実に由来しており、この名前が付けられています。

バブルソートアルゴリズムは次のように動作します: (後ろから前へ)

1. 隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。
2. 隣接する要素の各ペアに対して、最初の最初のペアから最後の最後のペアまで同じ作業を実行します。この時点では、最後の要素が最大の数値である必要があります。
3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。
4.比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

テキストの説明では理解できないかもしれませんが、コードを見てください:

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//冒泡排序
function BubbleSort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    //从后往前逐层上浮小的元素
    for($j = $length - 2;$j >= $i;$j --){
      //两两比较相邻记录
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
      }
    }
  }
}

バブルソートアルゴリズムの改善:

上記のバブルソートアルゴリズムはまだ最適化できますか?答えは「はい」です。想像してみてください。並べ替えたいシーケンスが {2,1,3,4,5,6,7,8,9} である場合、つまり、最初と 2 番目のキーワードを除いて、他のすべてを交換する必要があるとします。 . それはもう通常の順序です。 i = 0、2、1 が交換されるとき、この時点のシーケンスは既に整っていますが、アルゴリズムは依然として i = 2 ～ 9 と j ループを実行しますが、データは交換されませんが、多数の比較が行われます。以下はほとんど冗長でした。
i = 2 の場合、データ交換なしで 9 と 8、8 と 7、...、3 と 2 をすでに比較しています。これは、このシーケンスがすでに適切であり、後続のシーケンスを続行する必要がないことを意味します。判定作業（以降の作業ではデータのやり取りが発生しないため、再度行うことは無意味です）。このアイデアを実現するには、コードを改善し、このアルゴリズムの改善を実現するためのマーク変数フラグを追加する必要があります:

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
/冒泡排序的优化(如果某一次循环的时候没有发生元素的交换，则整个数组已经是有序的了)
function BubbleSort1(array &$arr){
  $length = count($arr);
  $flag = TRUE;
  for($i = 0;($i < $length - 1) && $flag;$i ++){
    $flag = FALSE;
    for($j = $length - 2;$j >= $i;$j --){
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
        $flag = TRUE;
      }
    }
  }
}

コード変更の鍵は、for ループにフラグが true であるかどうかを追加することです。 i 変数判定の このような改善の後、バブル ソートのパフォーマンスが向上し、順序がすでに整っている場合の無意味なループ判定を回避できます。

バブル アルゴリズムの合計時間計算量は O(n^2) です。

バブルソートは安定したソートです。

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨書籍:

PHP ヒルソートケース分析

PHP ヒープソートアルゴリズム例分析

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