思路分析

计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序

/**
  * 计数排序
  * @param $arr
  * @return array
  */
 function countingSort($arr)
 {
     $len = count( $arr );
     if( $len <= 1 ) return $arr;
     // 找出待排序的数组中最大值和最小值
     $min = min($arr);
     $max = max($arr);
     // 计算待排序的数组中每个元素的个数
     $countArr = array();
     for($i = $min; $i <= $max; $i++)
     {
         $countArr[$i] = 0;
     }
     foreach($arr as $v)
     {
         $countArr[$v] +=  1;
     }
     $resArr = array();
     foreach ($countArr as $k=>$c) {
         for($i = 0; $i < $c; $i++)
         {
             $resArr[] = $k;
         }
     }
     return $resArr;
 }

小结：

时间复杂度：O(n + k)

空间复杂度：O(k)

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序属于稳定排序