算法笔记-桶排序、计数排序、基数排序

//先引用之前的 快排的代码
function quickSort(array &$a)
{
    $n = count($a);
    quickSortInternally($a, 0, $n - 1);
}

function quickSortInternally(array &$a, int $l, int $r)
{
    if ($l >= $r) return;

    $q = partition($a, $l, $r);
    quickSortInternally($a, $l, $q - 1);
    quickSortInternally($a, $q + 1, $r);
}

function partition(&$a, $l, $r): int
{
    $pivot = $a[$r];
    $i = $l;

    for ($j = $l; $j < $r; ++$j) {
        if ($a[$j] < $pivot) {
            [$a[$j], $a[$i]] = [$a[$i], $a[$j]];
            ++$i;
        }
    }

    [$a[$r], $a[$i]] = [$a[$i], $a[$r]];

    return $i;
}

/**
 * 桶排序
 * 假设一个桶只能放置10个元素
 * 当一个桶内元素过多，需要继续分桶
 * @param array $numbers
 * @param [type] $size
 *
 * @return void
 * @date 2018/11/25
 * @author yuanliandu 
 */
function bucketSort(array $numbers) {
    $min = min($numbers);
    $max = max($numbers);
    $length = count($numbers);
    $bucketNumber =  ceil(($max-$min)/$length) + 1;
    $buckets = [];
    foreach($numbers as $key => $value) {
        $index = ceil(($value-$min)/$length);
        $buckets[$index][] = $value; 
    }
    
    $result = [];
    for($i=0;$i<$bucketNumber;$i++) {
        $bucket = $buckets[$i];
        $length = count($bucket);
        //如果桶内元素为空，跳过这个桶
        if($length == 0) {
            continue;
        }
        if( $length > 10) {
            $bucket = bucketSort($bucket,$length);
        }

       quickSort($bucket,0,count($bucket)-1);
       $result = array_merge($result,$bucket);
   }
   return $result;
}

$numbers = [11, 23, 45, 67, 88, 99, 22, 34, 56, 78, 90, 12, 34, 5, 6, 91, 92, 93, 93, 94, 95, 94, 95, 96, 97, 98, 99, 100];
$size = 10;
print_r(bucketSort($numbers, 10));

<?php

/**
 * 计数排序
 * 五分制
 * 13个人
 */
$score = [0, 1, 5, 3, 2, 4, 1, 2, 4, 2, 1, 4, 4];
print_r(countingSort($score));

function countingSort(array $score)
{

    $length = count($score);
    if ($length <= 1) {
        return $score;
    }

    /**
     * 统计每个分数的人数
     */
    $temp = [];
    $countScore = [];
    foreach ($score as $key => $value) {
        @$countScore[$value]++;
    }

    /**
     * 顺序求和
     */
    for ($i = 1; $i <= 5; $i++) {
        $countScore[$i] += $countScore[$i - 1];
    }
    /**
     * 排序
     */
    foreach ($score as $key => $value) {
        $countScore[$value]--;
        $temp[$countScore[$value]] = $value;
    }
    //copy
    for ($i = 0; $i < $length; $i++) {
        $score[$i] = $temp[$i];
    }
    return $score;
}

<?php

/**
 * 基数排序
 * 先根据个位排序、百位、千位........
 */
$numbers = [
    1234,
    4321,
    12,
    31,
    412,
];
$max = (string)max($numbers);//求出最大数字
$loop = strlen($max);//计算最大数字的长度，决定循环次数

for ($i = 0; $i < $loop; $i++) {
    radixSort($numbers, $i);
}
print_r($numbers);

/**
 * 基数排序
 * @param array $numbers
 * @param [type] $loop
 */
function radixSort(array &$numbers, $loop)
{

    $divisor = pow(10, $loop);//除数  主要决定比较个位数、百位.....
    $buckets = (new \SplFixedArray(10))->toArray();
    foreach ($numbers as $key => $value) {
        $index = ($value / $divisor) % 10;//计算该数字在哪个桶中
        $buckets[$index][] = $value;
    }
    /**
     * 从桶中取出数字
     */
    $k = 0;
    for ($i = 0; $i < 10; $i++) {
        while (count($buckets[$i]) > 0) {
            $numbers[$k++] = array_shift($buckets[$i]);
        }
    }
}