基数排序

---

基数排序(Radix Sort)

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

算法描述

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序(利用计数排序适用于小范围数的特点)。

动图演示

代码实现

$arr = [20, 40, 60, 80, 30, 70, 90, 10, 50, 0, 5];
//$arr = [31, 4.3, 4.1, 4.2, 5, 9, 0, 0];

/**
 * @param $value
 * @return int
 * 求最大位数
 */
function getMaxDigit($value)
{
    $maxDigit = 0;
    while ($value > 0) {
        $value = floor($value / 10);
        $maxDigit++;
    }
    return $maxDigit;
}

/**
 * @param $arr
 * @return mixed
 * 基数排序
 */
function radixSort($arr)
{
    $radix = 10; // 余数,求余,基数(十进制整数10个桶足矣)
    $dev = 1; // 除数,取整

    $arrSize = count($arr);
    $buckets = [];

    $maxDigit = getMaxDigit(max($arr)); // 位数,最大值
    // 位数决定循环次数
    for ($i = 0; $i < $maxDigit; $i++, $dev *= $radix, $radix *= $radix) {
        // 将数组元素入桶
        for ($j = 0; $j < $arrSize; $j++) {
            $pos = floor(($arr[$j] % $radix) / $dev); // 求数组元素的桶下标
            if (!isset($buckets[$pos])) {
                $buckets[$pos] = []; // 初始化
            }
            array_push($buckets[$pos], $arr[$j]); // 入桶
        }

        $index = 0; // 哨兵
        // 对每个桶进行循环出栈
        for ($j = 0; $j < $radix; $j++) {
            // 过滤无元素的桶
            if (isset($buckets[$j])) {
                // 使用第三方对数据进行桶里修正
//                bubbleSort($buckets[$j]);
                // 出队
                $value = array_shift($buckets[$j]);
                // 排队等于0的情况
                while ($value !== null) {
                    $arr[$index++] = $value;
                    $value = array_shift($buckets[$j]);
                }
            }
        }
    }

    return $arr;
}

/**
 * @param $arr
 * 冒泡排序
 */
function bubbleSort(&$arr)
{
    $arrSize = count($arr); // 大小,数组
    // 总共n次循环,每完成一趟排序,则有一个元素冒泡成功
    for ($i = 0; $i < $arrSize; $i++) {
        // 最后一个元素不用排序,已冒泡成功的不用排序
        for ($j = 0; $j < $arrSize - 1 - $i; $j++) {
            // 如果当前元素大小后继元素,则交换
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j + 1];
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
}

$arr = radixSort($arr);
var_dump($arr);

算法分析

基数排序基于分别排序，分别收集，所以是稳定的。 但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度， 而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。 假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n)，当然d要远远小于n， 因此基本上还是线性级别的。 基数排序的空间复杂度为O(n+k),其中k为桶的数量。 一般来说n>>k，因此额外空间需要大概n个左右。