计数排序

假设数组中有20个随机整数，取值范围为0～10，要求用最快的速度把这20个整数从小到大进行排序。
如何给这些无序的随机整数进行排序呢？
考虑到这些整数只能够在0、1、2、3、4、5、6、7、8、9、10这11个数中取值，取值范围有限。所以，可以根据这有限的范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0。

image.png

假设20个随机整数的值如下所示。
9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9
下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加1操作。
例如第1个整数是9，那么数组下标为9的元素加1。

image.png
第2个整数是3，那么数组下标为3的元素加1。
image.png
继续遍历数列并修改数组……
最终，当数列遍历完毕时，数组的状态如下。
image.png

有了这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。
0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10
显然，现在输出的数列已经是有序的了。
具体代码如下：

class Code{

    function countSort($arr){
        //1.求数组最大值
        $intMax = $arr[0];
        foreach ($arr as $key => $value) {
            if($value > $intMax){
                $intMax = $value;
            }
        }
        //2.根据数列最大值确定统计数组的长度
        $arrCount = array();
        for ($i=0; $i < $intMax+1; $i++) { 
            $arrCount[$i] = 0;
        }
        //3.遍历数列，填充统计数组
        foreach ($arr as $key => $value) {
            $arrCount[$value]++;
        }
        //4.遍历统计数组，输出结果
        $arrReturn = array();
        foreach ($arrCount as $key => $value) {
            for($i=0;$i<$value;$i++){
                $arrReturn[] = $key;
            }
        }
        return $arrReturn;
    }

    //运行
    function run(){
        $arr = array(8,5,7,4,2,0,1,3,9);
        $arr = $this->countSort($arr);
        print_r($arr);
    }
    
}
$obj = new Code();
$obj->run();

输出结果：

image.png

计数排序优化：
只以数列的最大值来决定统计数组的长度，其实并不严谨。例如下面的数列。
95，94，91，98，99，90，99，93，91，92
这个数列的最大值是99，但最小的整数是90。如果创建长度为100的数组，那么前面从0到89的空间位置就都浪费了！
很简单，只要不再以输入数列的最大值+1作为统计数组的长度，而是以数列最大值-最小值+1作为统计数组的长度即可。