计数排序（Counting sort）是一种根据小整数键对一组对象排序的算法；也就是说，它是一个整数排序算法。它通过计算具有不同键值的对象的数量，并对这些数量使用算术来确定输出序列中每个键值的位置。

计数排序只适合使用在键的变化不大于元素总数的情况下。它通常用作另一种排序算法（基数排序）的子程序，这样可以有效地处理更大的键。

总之，计数排序是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C ，其中第i个元素是待排序数组 A中值等于 i的元素的个数。然后根据数组C 来将A中的元素排到正确的位置。

通常计数排序算法的实现步骤思路是：

1.找出待排序的数组中最大和最小的元素；

2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

4.反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。

PHP计数排序算法的实现代码示例如下：

1. <?php 
2.  
3. function counting_sort($my_array, $min, $max) 
4.  
5. { 
6.  
7.     $count = array(); 
8.  
9.     for($i = $min; $i <= $max; $i++) 
10.  
11.     { 
12.  
13.         $count[$i] = 0; 
14.  
15.     } 
16.  
17.  
18.  
19.     foreach($my_array as $number) 
20.  
21.     { 
22.  
23.         $count[$number]++; 
24.  
25.     } 
26.  
27.     $z = 0; 
28.  
29.     for($i = $min; $i <= $max; $i++) { 
30.  
31.         while( $count[$i]-- > 0 ) { 
32.  
33.             $my_array[$z++] = $i; 
34.  
35.         } 
36.  
37.     } 
38.  
39.     return $my_array; 
40.  
41. } 
42.  
43. $test_array = array(3, 0, 2, 5, -1, 4, 1); 
44.  
45. echo "原始数组 :\n"; 
46.  
47. echo implode(', ',$test_array ); 
48.  
49. echo "\n排序后数组\n:"; 
50.  
51. echo implode(', ',counting_sort($test_array, -1, 5)). PHP_EOL; 

输出：

原始数组 : 3, 0, 2, 5, -1, 4, 1

排序后数组 :-1, 0, 1, 2, 3, 4, 5

Tags: php计数排序

分享到：