计数排序基于以下思想:通过将不同元素的值与数组的索引号映射，对不同元素的出现次数进行计数并将其存储在另一个数组（例如频率数组）中。然后迭代频率数组以使用不同的元素及其出现次数，并以排序的方式将它们放入输出数组中。
示例:
为了理解计数排序，让我们考虑一下未排序的数组 A = [9, 1, 2, 5, 9, 9, 2, 1, 3, 3] 并讨论按升序对数组进行排序所采取的每个步骤。
第1步:在这一步中，找出A[]中最大的元素，即(9) 另一个名为频率 的数组以大小[max(A[ ])+1] 启动。然后迭代数组 A[ ]，通过将不同元素与索引号 频率映射来存储 频率 数组中每个不同元素的出现次数 数组。
第 2 步:在此步骤中，迭代频率数组以获取有关每个不同元素及其出现次数的信息，以供进一步使用构建排序数组。
当输入元素的范围不显着大于要排序的元素数量时，计数排序的使用效率最高。除此之外，同样的概念也可以用于负输入数据。
计数排序的实现
<?php
// 计数排序函数
function countingsort(&$Array, $n) {
$max = 0;
//查找数组中最大的元素
for ($i=0; $i<$n; $i++) {
if($max < $Array[$i]) {
$max = $Array[$i];
}
}
//创建一个freq数组来存储出现的次数
//给定数组中的每个唯一元素
for ($i=0; $i<$max+1; $i++) {
$freq[$i] = 0;
}
for ($i=0; $i<$n; $i++) {
$freq[$Array[$i]]++;
}
//使用freq数组对给定数组进行排序
for ($i=0, $j=0; $i<=$max; $i++) {
while($freq[$i]>0) {
$Array[$j] = $i;
$j++;
$freq[$i]--;
}
}
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(9, 1, 2, 5, 9, 9, 2, 1, 3, 3);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
countingsort($MyArray, $n);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上面的代码将给出以下输出:
原始数组
9 1 2 5 9 9 2 1 3 3
排序数组
1 1 2 2 3 3 5 9 9 9 时间复杂度:
迭代输入数据的时间复杂度为θ(N)，其中N是未排序数组中的元素数量以及迭代频率数组的时间复杂度为θ(K)，其中K是输入范围数据。在所有情况下，计数排序的总体时间复杂度均为 θ(N+K)。