php实现计数排序（Counting Sort）

计数排序

        基本思想: 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

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

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

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

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

图片描述

代码实现(php）

<?php
    $arr=array(1,2,3,5,2,3,9,8,3,2,7,4,9,8,0,4,587,93); 
    printArr($arr); 
    echo "<hr>"; 
    function counting_sort(&$arr){ 
        $arr_=array(); 
        $cnt=0; 
        $len=count($arr); 
        for($i=0;$i<$len;$i++){//从第一个开始找比它小的数有多少个 
            $cnt=0; 
            for($j=0;$j<$len;$j++) 
                if($arr[$i]>$arr[$j]) 
                    $cnt++;        //计数比他小的有多少个 
            while($arr_[$cnt]!=0 && $cnt<$len) 
                $cnt++;            //对于相等的数，那么$arr_一定不为0，则cnt向前走一位进行存储 
            $arr_[$cnt]=$arr[$i]; 
        } 
        for($i=0;$i<$len;$i++) 
            $arr[$i]=$arr_[$i]; 
    } 
    counting_sort($arr); 
    printArr($arr); 
    function printArr($arr){ 
        for($i=0;$i<count($arr);$i++) 
            echo ' '.$arr[$i]; 
        echo "\n"; 
    }