1. 概述

  • 思路：创建数组，以值为键，出现次数为值，再对各数进行累加（比如0出现2次，1出现3次：[0=>2, 1=>3]。累加：[0=>2, 1=>5]。），然后对原序进行逆向迭代每个值，根据累加位置填入到新的有序数组中。
  • 稳定性：稳定

  • 其他：计数排序是桶排序的特例

    2. 实现代码

    ```php <?php //设定脚本执行时间限制 set_time_limit(0); //最大可用内存 ini_set(‘memory_limit’, -1); class CountSort { private $ori = []; public $new = []; public function __construct(array $arr) {

    1.   $this->ori = $arr;
    2.   $r = $this->count($this->ori);
    3.   $this->new = $r;

    }

    private function count(array $arr) {

    1.   // 分布
    2.   $map = [];
    3.   for ($i = 0; $i < count($arr); $i++) {
    4.       $map[$arr[$i]]++;
    5.   }
    6.   ksort($map);
    8.   // 分布累加
    9.   $pre = key($map);
    10.   foreach ($map as $k => $v) {
    11.       if ($k != $pre) {
    12.           $map[$k] += $map[$pre];
    13.           $pre = $k;
    14.       }
    15.   }
    17.   // 生成新数组
    18.   $ret = new SplFixedArray(count($arr));
    19.   $arr = array_reverse($arr, true);
    20.   foreach ($arr as $v) {
    21.       $ret[--$map[$v]] = $v;
    22.   }
    24.   return $ret;

    } }

// 1000万考生，成绩排序 $count = 10100100*100; for ($i = 0; $i <= $count; $i++) { $arr[] = rand(0, 750); } $starttime = explode(‘ ‘,microtime()); echo microtime(); $cls = new CountSort($arr); $endtime = explode(‘ ‘,microtime()); $thistime = $endtime[0]+$endtime[1]-($starttime[0]+$starttime[1]); $thistime = round($thistime,3); echo “本网页执行耗时：”.$thistime.” 秒。”.time();

// 少量数据 // $arr = [0,1,2,1,0,1,1,0,-3]; // $cls = new CountSort($arr); // echo implode(‘,’, $cls->new); ```