PHP实现-桶排序
2018-03-20 14:56 By
"Powerless"
3353
0
2
思路分析
假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)
/**
* 木桶排序设计
* @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），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
桶排序属于稳定排序
View in WeChat
Others Discussion
-
2016年云计算热词 Posted on 2019-06-12 17:53
-
PHP没你想的那么差 Posted on 2021-12-17 15:40
-
Mysql联合索引的最左前缀匹配原则 Posted on 2018-08-25 15:00
-
巧用CAS解决数据一致性问题 Posted on 2019-03-07 11:55
-
分布式架构之「 数据分布」 Posted on 2019-11-14 10:00
-
PHP扩展ImageMagick安装 Posted on 2022-11-11 11:16
-
通过信鸽来解释HTTPS Posted on 2018-10-22 13:56
-
HTTP和HTTPS的区别 Posted on 2020-08-10 23:00
评 论