PHP排序演算法系列之桶排序的詳解

這篇文章主要為大家詳細介紹了PHP排序演算法系列之桶排序，具有一定的參考價值，有興趣的小夥伴們可以參考一下

桶排序

#桶排序（Bucket sort）或所謂的箱排序，是一個排序演算法，工作的原理是將陣列分到有限數量的桶裡。每個桶再個別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間（Θ(n)）。但桶排序並不是比較排序，他不受O(n log n)下限的影響。

原理

設定一個定量的陣列當作空桶。
尋訪序列，並且把項目一個一個放到對應的桶子去。
對每個不是空的桶子進行排序。
從不是空的桶子裡把項目再放回原來的序列中。

範例

假定待排數字[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排序演算法系列之歸併排序詳解_php技巧

PHP排序演算法系列之直接選擇排序的詳解

############PHP排序演算法系列之插入排序的詳解############ ################

以上是PHP排序演算法系列之桶排序的詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！