计数排序

---

计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项;
• 对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加);
• 反向填充目标数据：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

动图演示

代码实现

$arr = [20, 40, 60, 80, 30, 70, 90, 10, 50, 0, 5];
$arr = [3, 2, 4, 1, 5, 9, 0, 0];
/**
 * @param $arr
 * @return mixed
 * 计数排序
 */
function countingSort($arr)
{
    $arrSize = count($arr); // 取数组总数
    $maxSize = max($arr) + 1; // 取数组中最大值,加1
    $bucket = array_fill(0, $maxSize, 0); // 建立额外存储空间(桶数组)
    // 将元素放入对应的桶数组下标
    for ($i = 0; $i < $arrSize; $i++) {
        if (!$bucket[$arr[$i]]) {
            $bucket[$arr[$i]] = 0;
        }
        $bucket[$arr[$i]]++;
    }
    // 将桶数组元素抛出
    $index = 0; // 哨兵
    for ($j = 0; $j < $maxSize; $j++) {
        while ($bucket[$j] > 0) {
            $arr[$index++] = $j;
            $bucket[$j]--;
        }
    }

    return $arr;
}

$arr = countingSort($arr);
var_dump($arr);

算法分析

计数排序是一个稳定的排序算法。 当输入的元素是n个0到k之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k), 其排序速度快于任何比较排序算法。 当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。