[PHP知识库]计数排序PHP实现

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。?[1]??当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

<?php

/**
 * 计数排序。
 * 时间复杂度为O(n)，但是会占用大量的内容空间
 * 当数值较小切为整数的时候可以采用
 * 非比较的一种稳定的排序
 */
$arr = [3,1,1,234,234,12,44,3,1,2,555,666];


$min = min($arr);
$max = max($arr);

Countingsort($min,$max,$arr);

function Countingsort($min,$max,$arr)
{

    //初始化,先占据一段空间
    for($i = $min ;$i<=$max;$i++){
        $cao[$i] = 0;
    }


    //排序
    foreach($arr as $v){
        $cao[$v]++;
    }
    //输出
    foreach($cao as $key =>$v){
        for($j=0;$j<$v;$j++){
            echo $key.'__';
        }
    }
}