迹忆客 专注技术分享

基数排序（Radix Sort）：是一种非比较型的整数排序算法。

基数排序的基本原理是，按照整数的每个位数分组。在分组过程中，对于不足位的数据用0补位。

基数排序按照对位数分组的顺序的不同，可以分为LSD基数排序和MSD基数排序。

LSD基数排序，是按照从低位到高位的顺序进行分组排序。例如：1,2,3,4,5,6,7,8,9,10第一次分组后为 10,1,2,3,4,5,6,7,8,9。

MSD基数排序，是按照从高位到低位的顺序进行分组排序。例如：1,2,3,4,5,6,7,8,9,10 第一次分组以后为 1,10,2,3,4,5,6,7,8,9。

上述两种方式不仅仅是对位数分组顺序不同，其实现原理也是不同的。这里我们只先介绍LSD基数排序。

首先我们看LSD基数排序是如何进行的

对于序列中的每个整数的每一位都可以看成是一个桶，而该位上的数字就可以认为是这个桶的键值。这句话应该怎么理解呢，我们来看这样的一个序列

170, 45, 75, 90, 802, 2, 24, 66

这是一个整数序列，我们知道，对于每个整数的每一位上的值肯定是介于0和9之间的。因此，要想对这个序列进行LSD排序，那就必须有10个桶。这10个桶的索引分别就是0——9这十个数。对于LSD基数排序来说，每一次分组过程就是将相应的整数放进相应的桶中。

拿第一次分组来说吧，对于每个整数要按照个位上的数进行分组。那么我们看170，其个位为0，所以说170应该放进0这个桶中。然后以此类推 45放在5这个桶中。

所以上述序列的第一次分组后，各个整数所在的桶如下

0: 170, 090
1: 空
2: 802, 002
3: 空
4: 024
5: 045, 075
6: 066
7–9: 空

然后再将这些数依次收集起来，第一次分组再组合以后的序列为

170, 90, 802, 2, 24, 45, 75, 66

接着就是针对十位上的数进行分组入桶，入桶的情况如下

0: 802, 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 170, 075
8: 空
9: 090

再次整理起来以后为下面的序列

802, 2, 24, 45, 66, 170, 75, 90

最后再次进行第三次（百位上的数）分组入桶

0: 002, 024, 045, 066, 075, 090
1: 170
2–7: 空
8: 802
9: 空

整理起来以后，我们发现整个序列已经是有序的了

2, 24, 45, 66, 75, 90, 170, 802

整个LSD基数排序的过程就是这样的，当然不同的程序可以构造不同的存放数据的桶的形式。但是其原理是相同的。

LSD基数排序是一个快速的稳定排序算法。其时间复杂度可以表示为O(Kn)。其中n就是待排序序列的元素个数，K是数字的位数。对于这个K我们应该怎样理解这个需要为大家说明一下。有时候K可以看做是一个常数——对于上述例子，其中K就是3。因为在上面的例子中最大的数是802，该数有3位。因此，在这种情况下，基数排序要比任何比较型的排序算法的效率要高。因为在比较型的排序算法中，最优的排序算法的时间复杂度也是O（nlogn）。

但是在一般情况下，K并不能再被认为是个常数。那K应该是什么呢。这里我们以十进制的数为例。整数序列中的每个数是以10为底的数。不妨我们用b记为底数，即b=10。那如果整个整数序列中的最大数是N。那这就很容易看出，K= log_bN。所以在一般情况下，基数排序的时间复杂度可以看做是O（n log_bN）。在N非常大的情况下是不是基数排序的效率要低于比最优的比较型的排序算法（最优的比较型的排序算法的时间复杂度是O（nlogn））。现在让我们假设N <= n^c ，这里c是一个常数。这种情况下基数排序的时间复杂度就变成了O（n log_bn）。但是即使这样，也不能比复杂度是O（nlogn）的比较型排序算法更快。那如果我们使b的值变大呢？如果我们使得b的值为n的话，这样基数排序的时间复杂度是不是就变成了线性的了，即O（n）。也就是说，如果待排序的序列的数是以n为底的话，那序列中的数可以是1到n^c 之间的数。其时间复杂度就是线性的。

好了，对于基数排序的效率问题，我们就先讨论到这里。接下来就该进入我们的核心问题——LSD基数排序代码的实现。

/**
 * 找到序列中最大位数
 */
function FindMaxBit($arr){
    /*
     * 首先查找序列中最大的数
     */
    $p = $arr[0];
    for($i=1;$i<count($arr);$i++){
        if($arr[$i]>=$p){
            $p = $arr[$i];
        }
    }
    //得到最大的数以后，计算出该数据有多少位
    $d = 1;
    while(floor($p/10)>0){
        $d++;
        $p = floor($p/10);
    }
    return $d;
}
function LSD_RadixSort(&$arr){
    //得到序列中最大位数
    $d = FindMaxBit($arr);
    $bucket = array();
    //初始化队列
    for($i=0;$i<10;$i++){
        $bucket[$i]=array('num'=>0,'val'=>array());
    }
    /*
     * 开始进行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i++){
        for($j=0;$j<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $bucket[$k]['num']++;
            array_push($bucket[$k]['val'],$arr[$j]);
        }
        $arr = array();
        foreach ($bucket as $key => $val) {
            for ($j = 0; $j < $val['num']; $j ++) {
                $arr[] = $val['val'][$j];
            }
        }
        for($l=0;$l<10;$l++){
            $bucket[$l]=array('num'=>0,'val'=>array());
        }
        $radix *= 10;
    }
}
$arr = array(
    15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
    224,765,980,159,456,7,998,451,96,0,673,82,91,100
);
LSD_RadixSort($arr,0,count($arr)-1);
print_r($arr);

在上面的代码中，我是将实际的数据直接存放在桶中了。然后将桶中的数据按照顺序覆盖掉原队列中的数据。然后再次将被覆盖后的队列进行分组，依次进行下去。

当然还有一种方式就是，申请一个和原序列相同大小的队列（不妨成为临时队列），然后再申请一个用于作桶的数组。桶中只是存放原序列中的数在临时队列中的位置，然后将原序列中的数按照桶中的顺序放入临时队列中。然后将临时队列整个赋值给原序列。

二者虽然实现方式不同，但是其空间复杂度是相同的。下面我们看后者应该如何用代码实现。

function LSD_RadixSort(&$arr){
    //得到序列中最大位数
    $d = FindMaxBit($arr);
    $bucket = array();
    $temp = array();
    //初始化队列
    for($i=0;$i<10;$i++){
        $bucket[$i] = 0;
    }
    /*
     * 开始进行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i++){
        for($j=0;$j<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $bucket[$k]++;
        }
        //在桶中调整原序列在临时队列中的位置
        for($j=1;$j<10;$j++){
            $bucket[$j] += $bucket[$j-1];
        }
        for($j=count($arr)-1;$j>=0;$j--){
            $k = floor($arr[$j]/$radix)%10;
            $temp[--$bucket[$k]] = $arr[$j];
        }
        /*
         * 将临时队列赋值给原序列
         */
        for($j=0;$j<count($temp);$j++){
            $arr[$j] = $temp[$j];
        }
        for($j=0;$j<10;$j++){
            $bucket[$j] = 0;
        }
        $radix *= 10;
    }
}

上述就是对基数排序的基本介绍。希望这些能对大家有所帮助。