当前位置:首页 > PHP教程 > php应用 > 列表

php计数排序算法的实现(代码示例)

发布:smiling 来源: PHP粉丝网  添加日期:2020-01-29 10:21:34 浏览: 评论:0 

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

分享到: