计数排序php实现,PHP 计数排序 ，适用与范围内排序
// 计数排序算法
# 适用于一定范围内的排序
function countSort ($arr) {
$count = count($arr);
# 获取最大的元素max、min
$max = $min = $arr[0];
# 范围为min ~ max 构建统计数组
$new = [];
# 便利数组填充 统计数组
for ($j = 0; $j < $count; $j++) {
if ($arr[$j] > $max) {
$max = $arr[$j];
}
if ($arr[$j] < $min) {
$min = $arr[$j];
}
if (isset($new[ $arr[$j] ])) {
$new[$arr[$j]]++;
}else {
$new[$arr[$j]] = 1;
}
}
# 便利数组输出结果
$str = [];
for ($k = $min; $k <= $max; $k++) {
if ($new[$k] == 0) {
continue;
}
// echo $new[$k] . "\n";
$n = 0;
while ($n <= $new[$k] - 1) {
$n++;
array_push($str, $k);
}
}
return $str;
}
$arr = [4,4,6,5,3,2,8,1,7,5,6,0,10,9,4,6,3];
$res = countSort($arr);
print_r(implode(",", $res));
echo "\n";
// 优化 (针对重复值。稳定排序)
function newCountSort($arr) {
$count = count($arr);
# 获取最大、最小元素max、min
$max = $min = $arr[0];
for ($i = 0; $i < $count; $i++) {
if ($arr[$i] > $max) {
$max = $arr[$i];
}
if ($arr[$i] < $min) {
$min = $arr[$i];
}
}
// echo $max . "\t" . $min . "\n";die;
# 获取差值
$difference = $max - $min;
# 创建统计数组并统计对应元素个数(如果不减？默认已原值做键值)
$new = [];
for ($j = 0; $j < $count; $j++) {
if (isset($new[$arr[$j] - $min])) {
$new[$arr[$j] - $min]++;
}else {
$new[$arr[$j] - $min] = 1;
}
}
# 统计数组做变形，后面的元素等于前面的元素之和
$sum = 0;
for ($i = 0; $i <= $difference ; $i++) {
if(!isset($new[$i])) {
continue;
}
$sum += $new[$i];
$new[$i] = $sum;
}
# 倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
$sort_arr = [];
for ($j = $count - 1; $j >= 0; $j--) {
$sort_arr[$new[$arr[$j] - $min] - 1] = $arr[$j];
$new[$arr[$j] - $min]--;
}
ksort($sort_arr); // 这里循环输出结果
return $sort_arr;
}
$arr = [56,57,53,55,54,50,52,59,51,54];
$res = newCountSort($arr);
print_r(implode(",", $res));
echo "\n";