PHP实现-桶排序


常见的排序算法有:冒泡排序,快速排序,选择排序,插入排序,本文对桶排序做了一个总结。

思路分析

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

/**
  * 木桶排序设计
  * @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),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。


桶排序属于稳定排序

上一篇 下一篇

评论

登录后可发表评论