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

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

小云云

リリース： 2023-03-19 11:06:02

オリジナル

1697 人が閲覧しました

この記事は主に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;
}

ログイン後にコピー