10基数排序

https://www.yduba.com/biancheng-6212544194.html

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。
排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序法会使用到桶，顾名思义，通过将要比较的位（个位、十位、百位…），将要排序的元素分配到0~9个桶中，借以达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法。

算法步骤
基数排序的方式可以采用 LSD (Least sgnificant digital) 或 MSD (Most sgnificant digital)，LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。 以 LSD 为例，假设原来有一串数值如下所示：
36 9 0 25 1 49 64 16 81 4
首先根据个位数的数值，按照个位值等于桶编号的方式，将它们分配至编号0至9的桶子中：

然后，将这些数字按照桶以及桶内部的排序连接起来：
0 1 81 64 4 25 36 16 9 49
接着按照十位的数值，分别对号入座：

最后按照次序重现连接，完成排序：
0 1 4 9 16 25 36 49 64 81

效率分析
基数排序的时间复杂度是O(k * n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n * log(n) )，k的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集大小；k决定了进行多少轮处理，而n是每轮处理的操作数目。
以排序n个不同整数来举例，假定这些整数以B为底，这样每位数都有B个不同的数字，k = log**BN，N是待排序数据类型全集的势。虽然有B个不同的数字，需要B个不同的桶，但在每一轮处理中，判断每个待排序数据项只需要一次计算确定对应数位的值，因此在每一轮处理的时候都需要平均n次操作来把整数放到合适的桶中去，所以就有：k ≈ log**BN ，所以，基数排序的平均时间$T$就是：T ≈ LogB(N) * n其中前一项是一个与输入数据无关的常数，当然该项不一定小于log n。
如果考虑和比较排序进行对照，基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小，而且在适当选择的$B$之下，k一般不大于log n，所以基数排序一般要快过基于比较的排序，比如快速排序。

算法稳定性
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优 先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

动图演示


代码实现

<?php
function GetNumInPos($number, $pos)
{
    $number = strrev( $number );
    return $number[ -- $pos ];
}
function LsdRadixSort(array $numbers = array(), $tpos=1) 
{
    $count = count( $numbers );
    if( $count <= 1 ) return $numbers;
    $bucket = array();
    for($i = 0; $i < 10; $i ++)
    {
        $bucket[$i] = array(0);
    }
    // 由低 $p=1 至高位 $p<=$d 循环排序
    for($p = 1; $p <= $tpos; $p ++) 
    {
        // 将对应数据按当前位的数值放入桶里
        for($i = 0; $i < $count; $i ++)
        {
            $n = GetNumInPos($numbers[$i], $p);
            $index = ++ $bucket[$n][0];
            $bucket[$n][$index] = $numbers[$i];
        }
        // 收集桶里的数据
        for($i = 0, $j = 0; $i < 10; $i ++) 
        {
            for($num = 1; $num <= $bucket[$i][0]; $num ++)
            {
                $numbers[$j++] = $bucket[$i][$num];
            }
            $bucket[$i][0] = 0;
        }
    }
    return $numbers;
}