思路分析

假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)

/**
  * 木桶排序设计
  * @param $arr 目标数组
  * @param int $bucketCount 分配的木桶数目（整数）
  * @return array
  */
 public function bucketSort($arr,$bucketCount = 10)
 {
     $len = count($arr);
     $max = max($arr)+1;
     if ($len <= 1) {return $arr;}
     //填充木桶
     $arrFill = array_fill(0, $bucketCount, []);
     //开始标示木桶
     for($i = 0; $i < $len ; $i++)
     {
         $key = intval($arr[$i]/($max/$bucketCount));
         array_push($arrFill[$key] , $arr[$i]);
         //TODO 测试发现：如果此处调用，耗时翻倍
         /*if(count($arrFill[$key])){
             $arrFill[$key] = $this->insertSort($arrFill[$key]);
         }*/
     }
     //对每个不是空的桶进行排序
     foreach ($arrFill as $key=>$f){
         if (count($f)){
             $arrFill[$key] = $this->insertSort($f);
         }
     }
     //开始从木桶中拿出数据
     for($i = 0; $i < count($arrFill); $i ++)
     {
         if($arrFill[$i]){
             for($j = 0; $j <= count($arrFill[$i]); $j++)
             {   //这一行主要用来控制输出多个数字
                 if ($arrFill[$i][$j]){
                     $arrBucket[] = $arrFill[$i][$j];
                 }
             }
         };
     }
     return $arrBucket;
 }

注： 上述代码是我根据对木桶排序的定义进行的设计，因为网上多数的PHP代码感觉不合规范，其中的insertSort()为借用前面所写的插入排序 通过测试发现，此方法耗时比countingSort()要长好多，此处仅做参考不做推荐。

小结：

时间复杂度：O(n + k)

空间复杂度：O(n + k)

当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

桶排序属于稳定排序