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

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

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

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

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

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

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

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

1. <?php 
2. function counting_sort($my_array, $min, $max) 
3. { 
4.   $count = array(); 
5.   for($i = $min; $i <= $max; $i++) 
6.   { 
7.     $count[$i] = 0; 
8.   } 
9.    
10.   foreach($my_array as $number) 
11.   { 
12.     $count[$number]++; 
13.   } 
14.   $z = 0; 
15.   for($i = $min; $i <= $max; $i++) { 
16.     while( $count[$i]-- > 0 ) { 
17.       $my_array[$z++] = $i; 
18.     } 
19.   } 
20.   return $my_array; 
21. } 
22. $test_array = array(3, 0, 2, 5, -1, 4, 1); 
23. echo "原始数组 :\n"; 
24. echo implode(', ',$test_array ); 
25. echo "\n排序后数组\n:"; 
26. echo implode(', ',counting_sort($test_array, -1, 5)). PHP_EOL; 

输出：

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

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

下面补充一个例子

1、计数排序只适用于整数在小范围内排序

1. <?php 
2. $arr = [95,94,91,98,99,90,99,93,91,92]; 
3. function countSort($arr){ 
4. $max = $arr[0]; 
5. $min = $arr[0]; 
6. for($i=0;$i<count($arr);$i++){ 
7. if($arr[$i]>$max){ 
8. $max = $arr[$i]; 
9. } 
10. if($arr[$i] < $min){ 
11. $min = $arr[$i]; 
12. } 
13. } 
14. try{ 
15. $frequency = new SplFixedArray($max-$min+1); 
16. for($i=0;$i<count($arr);$i++){ 
17. if(emptyempty($frequency[$arr[$i]-$min])) 
18. $frequency[$arr[$i]-$min] = 0; 
19. $frequency[$arr[$i]-$min] += 1; 
20. } 
21.  
22. $sum = 0; 
23. for ($i=0; $i < count($frequency); $i++) { 
24. $sum += $frequency[$i]; 
25. $frequency[$i] = $sum; 
26. } 
27.  
28. $splfixed = new SplFixedArray(count($arr)); 
29.  
30. for($i=(count($arr)-1);$i>=0;$i--){ 
31. $splfixed[$frequency[$arr[$i]-$min]-1] = $arr[$i]; 
32. $frequency[$arr[$i]-$min] -= 1; 
33. } 
34. }catch(RuntimeException $re){ 
35. echo "RuntimeException: ".$re->getMessage()."\n"; 
36. } 
37. print_r($splfixed->toArray()); 
38. } 
39. countSort($arr); 
40. ?> 

输出

1. Array 
2. ( 
3.     [0] => 90 
4.     [1] => 91 
5.     [2] => 91 
6.     [3] => 92 
7.     [4] => 93 
8.     [5] => 94 
9.     [6] => 95 
10.     [7] => 98 
11.     [8] => 99 
12.     [9] => 99 
13. ) 

2、php计数排序

获取序列中的最小值min和最大值max O(n)

统计min - max之间所有值在序列中的出现次数 O(n)

顺序输出min - max的所有值,次数为0不输出,其余次数为多少就输出多少 O(k) k为数据范围

例如序列为: 2, 4, 6, 9, 4, 8

min = 2, max = 9, n为6,k为8

统计出现次数为

[2 => 1, 3 => 0, 4 => 2, 5 => 0, 6 => 1, 7 => 0, 8 => 1, 9 => 1]

输出结果为

2, 4, 4, 6, 8, 9

很明显,计数排序的复杂度为O(n) + O(k),也就是和数据量和数据范围有关.

若n和k相近,则可认为是O(n)

同时,因为要统计出现次数,如果数据范围过大而数据又很稀疏,造成的空间浪费比较大

1. class CountSort 
2. { 
3.   private $originalData = []; 
4.   private $rangeMap = []; 
5.   private $resultData = []; 
6.  
7.   public function __construct($original = []) 
8.   { 
9.     $this->originalData = $original; 
10.   } 
11.  
12.   public function sort() 
13.   { 
14.     list($min, $max) = $this->calculateDataRange(); 
15.     $this->statisticNumberOfOccurrence($min, $max); 
16.     $this->resultData = $this->generateResult(); 
17.     return $this->resultData; 
18.   } 
19.  
20.   protected function calculateDataRange() 
21.   { 
22.     $max = null; 
23.     $min = null; 
24.  
25.     foreach ($this->originalData as $value) { 
26.       if (!is_null($max)) { 
27.         if ($value > $max) { 
28.           $max = $value; 
29.         } 
30.       } else { 
31.         $max = $value; 
32.       } 
33.  
34.       if (!is_null($min)) { 
35.         if ($value < $min) { 
36.           $min = $value; 
37.         } 
38.       } else { 
39.         $min = $value; 
40.       } 
41.     } 
42.  
43.     return [$min, $max]; 
44.   } 
45.  
46.   protected function statisticNumberOfOccurrence($min, $max) 
47.   { 
48.     for ($i = $min; $i <= $max; $i++) { 
49.       $this->rangeMap[$i] = 0; 
50.     } 
51.  
52.     foreach ($this->originalData as $value) { 
53.       $this->rangeMap[$value]++; 
54.     } 
55.   } 
56.  
57.   protected function generateResult() 
58.   { 
59.     $result = []; 
60.  
61.     foreach ($this->rangeMap as $key => $value) { 
62.       if ($value != 0) { 
63.         for ($i = 0; $i < $value; $i++) { 
64.           array_push($result, $key); 
65.         } 
66.       } 
67.     } 
68.     return $result; 
69.   } 
70. } 
71.  
72. $testData = [2, 3, 4, 3, 10, 30, 20, 15, 10, 12, 33]; 
73.  
74. $countSort = new CountSort($testData); 
75. echo '<pre>'; 
76. var_dump($countSort->sort()); 

输出

1. <pre>array(11) { 
2.   [0]=> 
3.   int(2) 
4.   [1]=> 
5.   int(3) 
6.   [2]=> 
7.   int(3) 
8.   [3]=> 
9.   int(4) 
10.   [4]=> 
11.   int(10) 
12.   [5]=> 
13.   int(10) 
14.   [6]=> 
15.   int(12) 
16.   [7]=> 
17.   int(15) 
18.   [8]=> 
19.   int(20) 
20.   [9]=> 
21.   int(30) 
22.   [10]=> 
23.   int(33) 
24. }

Tags: php计数排序算法

分享到：