PHPソートアルゴリズムバブルソート（Bubble Sort）-PHPチュートリアル-php.cn

PHPソートアルゴリズムバブルソート（Bubble Sort）

不言

リリース： 2023-03-24 14:18:02

オリジナル

1749 人が閲覧しました

この記事では、PHP ソートアルゴリズムのバブルソートの実装方法を主に紹介し、Dahua データ構造のアルゴリズムを参照し、バブルソートの原理と関連する実装テクニックをサンプルの形で詳細に分析することができます。以下を参照してください

この記事の例では、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);
      }
    }
  }
}

ログイン後にコピー

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

『Dahua Data Structure』は確かに良い本です。バブルソートアルゴリズムの改善を紹介しました。ここでそのステートメントを直接引用します:

上記のバブルソートアルゴリズムはまだ最適化できますか?答えは「はい」です。想像してみてください。並べ替えたいシーケンスが {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;
      }
    }
  }
}

ログイン後にコピー

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

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

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

この記事は「Dahua データ構造」から参照されています。将来の参考のためにここに記録されているだけです。批判しないでください。