今天重新看了看木桶排序,思路比较简单,这里整理一下,免得下次忘记。
假设要对一组数据 2 2 3 1 6 5 4 进行桶排序。
1.首先选出最小元素1和最大元素6,做一个桶,也就是定义一个1-6的数组,并且把他们的值都置为0。
2.遍历这个桶,每一步遍历桶都在该数组中查找是否有元素和这个桶的下标相等,如果有,则该桶中该下标对应的元素值自增1;
3.遍历桶,根据数组中元素在桶中出现的次数就可以排好序了,用一个数组保存结果并返回。
代码如下:
<?php $list = array(2,2,3,1,6,5,4); function backetSort($list){
$min = min($list);
$max = max($list);
//做桶,最小值到最大值全部用0填充
$arr = array_fill($min,$max-$min+1,0);
//入桶
foreach($list as $k=>$v){
$arr[$v]++;
} foreach($arr as $k=>$v){
for($i=1;$i<=$v;$i++){
$result[] = $k;
}
}
return $result;
} $list = backetSort($list); var_dump($list);