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] 空のバケット
#[0 1 2 3 4 5 6 7 8 9] バケット番号 (実際には存在しません)

1. ソート対象の配列から数値を順番に取り出します。まず 6 を取り出し、次に 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 ソート アルゴリズムのマージ ソートの詳細な説明 series_php スキル

PHP ソート アルゴリズム シリーズでの直接選択ソートの詳細説明

PHP ソート アルゴリズム シリーズでの挿入ソートの詳細説明

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