算法还是很重要嘀~
直接贴代码:
<?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;