算法还是很重要嘀~
直接贴代码:
<?php
/*
* count_sort.php 计数排序
* cli 模式运行 php count_sort.php 3 4 5 6 3 2 4 56 4 3 2 8 1
*/
$a = $argv;
unset($a[0]);
$n = count($a);
// 找出数组中最大的数
$k = 0;
for ($i = 1; $i <= $n; $i++) {
if ($k < $a[$i])
$k = $a[$i];
}
// 初始化数组 $c
$c[0]= 0;
for ($i = 1; $i <= $k; $i++)
$c[$i] = 0;
for ($i = 1; $i <= $n; $i++) {
$c[$a[$i]]++;
}// 此时 $c[$i] 包含等于 $i 的元素个数
for ($i = 1; $i <= $k; $i++) {
$c[$i] = $c[$i-1] + $c[$i];
}// 此时 $c[$i] 包含小于或等于 $i 的元素个数
for ($i = $n; $i >= 1; $i--) {
$b[$c[$a[$i]]] = $a[$i];
$c[$a[$i]]--;
}
// 输出已排好序的数组
for ($i = 1; $i <= $n; $i++)
echo $b[$i] . ' ';
echo "\n";
今天又重新梳理了一遍,不能根据这个代码看出计数排序是稳定排序:
<?php
/**
* 计数排序
*/
$nums = [23,12,23,34,23,456,23,12,23,45,23,12,1234];
$n = count($nums);
// 找出数组中最大的数
$max = $nums[0];
for ($i = 1; $i < $n; $i++) {
if ($max < $nums[$i]) {
$max = $nums[$i];
}
}
// 初始化用来计数的数组
for ($i = 0; $i <= $max; $i++) {
$cnt[$i] = 0;
}
// 下面的 for loop 处理完毕后,$cnt[$i] 表示待排序数组中,值等于 $i 的元素个数
for ($i = 0; $i < $n; $i++) {
$cnt[$nums[$i]]++;
}
// 下面的 for loop 处理完毕后,$cnt[$i] 表示待排序数组中,值小于等于 $i 的元素个数
for ($i = 1; $i <= $max; $i++) {
$cnt[$i] = $cnt[$i-1] + $cnt[$i];
}
// 这一步比较难理解
for ($i = $n-1; $i >= 0; $i--) {
$result[$cnt[$nums[$i]]] = $nums[$i];
$cnt[$nums[$i]]--; // 前一个数找到位置后,那么和它值相同的数位置往前一步
}
for ($i = 1; $i < $n; $i++) {
echo $result[$i], ' ';
}
echo PHP_EOL;