桶排序
大约 2 分钟
桶排序
桶排序(Bucket Sort)
桶排序是计数排序的升级版。 它利用了函数的映射关系,高效与否的关键就在于这个映射函数来确定。 桶排序(Bucket Sort)的工作原理: 假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序 (有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排);
算法描述
- 设置一个定量的数组当作空桶;
- 遍历输入数据,并且把数据一个一个放到对应的桶里去;
- 对每个不是空的桶进行排序;
- 从不是空的桶里把排好序的数据拼接起来。
图片演示
代码实现
$arr = [20, 40, 60, 80, 30, 70, 90, 10, 50, 0, 5];
//$arr = [3, 2, 4, 1, 5, 9, 0, 0];
const BUCKET_SIZE = 5; // 桶分配规则
/**
* @param $arr
* @return mixed
* 桶排序
*/
function bucketSort(&$arr)
{
$arrSize = count($arr); // 大小,数组
$minValue = min($arr); // 最小值,数组
$maxValue = max($arr); // 最大值,数组
$bucketCount = floor(($maxValue - $minValue) / BUCKET_SIZE) + 1; // 桶数量,用映射函数确定
$buckets = array_fill(0, $bucketCount, 0); // 桶数组,建立额外存储空间
// 桶初始化
for ($i = 0; $i < count($buckets); $i++) {
$buckets[$i] = [];
}
// 桶映射,用映射函数将数据分配到各个桶中
for ($i = 0; $i < $arrSize; $i++) {
array_push($buckets[floor(($arr[$i] - $minValue) / BUCKET_SIZE)], $arr[$i]);
}
$index = 0; // 哨兵
for ($i = 0; $i < $bucketCount; $i++) {
// 将各桶数据进行插入排序
insertionSort($buckets[$i]);
// 将桶数据出栈
for ($j = 0; $j < count($buckets[$i]); $j++) {
$arr[$index++] = $buckets[$i][$j];
}
}
}
/**
* @param $arr
* 插入排序
*/
function insertionSort(&$arr)
{
$arrSize = count($arr); // 大小,数组
for ($i = 1; $i < $arrSize; $i++) {
$current = $arr[$i]; // 当前元素放到暂存区
$preIndex = $i - 1; // 坐标,前一个元素
// 右移所有大于当前元素的元素
while ($preIndex >= 0 && $arr[$preIndex] > $current) {
$arr[$preIndex + 1] = $arr[$preIndex];
$preIndex--;
}
$preIndex++; // 补偿,退出循环条件使坐标变成了前前一个元素
$arr[$preIndex] = $current; // 插入到正确位置
}
}
bucketSort($arr);
var_dump($arr);
算法分析
桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决于对各个桶之间数据进行排序的时间复杂度, 因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。