8计数排序

https://www.yduba.com/biancheng-1362548964.html
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于对一定范围内的整数排序时，它的复杂度为O(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n))，如归并排序，堆排序）
算法步骤
1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项；
3. 依次统计出C[i]表示数组中小于等于i的元素出现的个数；
4. 从带排序列A的最后一个元素开始，将A[i]放到正确的位置（从后往前保证了排序的稳定性）。即前面又几个元素小于等于它，它就放在第几个位置。

效率分析
由计数排序的代码实现可以看出，计数排序总的时间代价为O(k+n)。在实际工作中，当k=O(n)时，我们一般会采用计数排序，这时的运行时间为O(n)。
计数排序需要两个额外的数组用来对元素进行计数和保存排序的输出结果，所以空间复杂度为O(k+n)。

算法稳定性
计数排序的一个重要性质是它是稳定的：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序是相同的。也就是说，对两个相同的数来说，在输入数组中先出现的数，在输出数组中也位于前面。
计数排序的稳定性很重要的一个原因是：计数排序经常会被用于基数排序算法的一个子过程。我们将在下一篇文章中介绍，为了使基数排序能够正确运行，计数排序必须是稳定的。

动图演示


代码实现

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