PHPソートアルゴリズムシリーズ バケットソート詳細解説_phpスキル

この記事は主にPHPソートアルゴリズムシリーズのバケットソートを皆さんに詳しく紹介していますので、興味のある方は参考にしていただければ幸いです。

バケット ソート

バケット ソート、またはいわゆるビン ソートは、配列を限られた数のバケットに分割することで機能する並べ替えアルゴリズムです。各バケットは個別に並べ替えられます (別の並べ替えアルゴリズムを使用したり、再帰的にバケットの並べ替えを使用し続けることも可能です)。バケット ソートは、鳩の穴ソートの帰納的な結果です。バケット ソートでは、ソート対象の配列内の値が均等に分散されている場合、線形時間 (Θ(n)) が使用されます。ただし、バケット ソートは比較ソートではないため、O(n log n) の下限の影響を受けません。

原則

定量配列を空のバケットとして設定します。
シーケンスを検索し、アイテムを対応するバケットに 1 つずつ入れます。
空ではない各バケットを並べ替えます。
空ではないバケットのアイテムを元のシーケンスに戻します。

例

ソートする数値を[6 2 4 1 5 9]とする

空バケツの最大数である10個の空バケツを用意する
[0 0 0 0 0 0 0 0 0 0] Empty buckets
[0 1 2 3 4 5 6 7 8 9] バケット番号(実際には存在しません)

1. ソート対象の数値をまず6を取り出し、次に6を取り出します。プロセスは次のようになります: 空のバケット [ソート対象の配列[ 0] ] = ソート対象の配列[ 0]

[6 2 4 1 5 9] ソート対象の配列
[ 0 0 0 0 0 0 6 0 0 0] 空のバケット
[0 1 2 3 4 5 6 7 8 9] バケット番号（実際には存在しません）

2. ソート対象の配列から次の番号を取り出します。 . このとき、2を取り出して2番のバケツに入れます。 何のバケツに入れるのですか

[6 2 4 1 5 9] 並べ替える配列
[0 0 2 0] 0 0 6 0 0 0] 空のバケット
[0 1 2 3 4 5 6 7 8 9] バケット番号 (実際には存在しません)

3,4,5,6 は省略されていますが、以降の処理は同じですすべてバケットに入れるとこうなります

[6 2 4 1 5 9] ソート対象の配列
[0 1 2 0 4 5 6 0 0 9] 空のバケット
[0 1 2 3 4 5 6] 7 8 9] バケット番号 (実際には存在しません)
0 は空のバケットを意味します。スキップして、順番に取り出してください: 1 2 4 5 6 9

PHP コード 実現

<?php
function bucket_sort($arr){
 $result=[];
 $length=count($arr);
 //入桶
 for($i=0,$max=$arr[$i];$i<$length;$i++){
  if ($max<$arr[$i]) {
   $max=$arr[$i];
  }
  $bucket[$arr[$i]]=[];
  array_push($bucket[$arr[$i]],$arr[$i]);
 }
 //出桶
 for($i=0;$i<=$max;$i++){
  if(!empty($bucket[$i])){
   $l=count($bucket[$i]);
   for ($j=0; $j <$l ; $j++) {
    $result[]=$bucket[$i][$j];
   }
  }
 }
 return $result;
}

関連する推奨事項:

PHPソートアルゴリズムのレビューとまとめ

PHPソートアルゴリズムのレビューとまとめ_PHPチュートリアル

PHPソート古典アルゴリズム_PHPチュートリアル

以上がPHPソートアルゴリズムシリーズ バケットソート詳細解説_phpスキルの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。