PHP 计数排序

孙吉亮发布于2019-07-01 10:25 / 2252人阅读

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

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

算法描述

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

/**
 * 计数排序: 桶排序的一种
 */
$arr = [5,69,4,32,14,8,74,95,23,56,41,5,31,63];
$length = count($arr);
$maxValue = $arr[0];

// 找出数组中的最大值
for ($i=1; $i < $length; $i++) {
    if ($arr[$i] > $maxValue) {
        $maxValue = $arr[$i];
    }
}
/**
 * 定长数组, 键会自动排序, PHP数组是hash表的实现,
 * 如果这里用普通的数组, 键不会自动排序, 不存在的键也不会自动填充null
 */
$frequency = new SplFixedArray($maxValue + 1);

/**
 * 统计arr中, 值出现的频次
 */
for ($i=0; $i < $length; $i++) {
    if(empty($frequency[$arr[$i]]))
        $frequency[$arr[$i]] = 0;
    $frequency[$arr[$i]] += 1;
}

// 清空$arr
$arr = [];
// 遍历frequency, 如果其元素有值, 那么将键push到arr中
for ($i=0; $i < count($frequency); $i++) {
    if (!empty($frequency[$i])) {
        for ($j=0; $j < $frequency[$i]; $j++) {
            $arr[] = $i;
        }
    }
}

print_r($arr);

参考文章: https://www.cnblogs.com/onepi...

GPU云服务器云服务器计数排序 php赋值科学计数法 php输出科学计数法 php 排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/29161.html

PHP数组排序算法实现(14种)

摘要：本文将介绍快速排序计数排序梳排序堆排序归并排序希尔排序选择排序插入排序地精排序联合冒泡排序鸡尾酒排序冒泡排序奇偶排序使用标志的冒泡排序种排序算法的实现。是一种不稳定的排序算法。本文将介绍快速排序、计数排序、梳排序、堆排序、归并排序、希尔排序、选择排序、插入排序、地精排序、联合冒泡排序、鸡尾酒排序、冒泡排序、奇偶排序、使用标志的冒泡排序14种排序算法的实现。本文是由于阅读了文章《测试评...

aisuhua 2019-06-27 13:54 评论0 收藏0
DUX主题7.4版本更新：新增文字LOGO、Ajax阅读数、点赞状态、后台阅读量排序等多项功能

摘要：主题的更新又来了，每次都不少，每次都是大更新。版本以上均可以安装，推荐在版本以上中使用最佳性能。dux主题的更新又来了，每次都不少，每次都是大更新。dux主题7.4版本更新内容主要：新增文字LOGO、Ajax阅读数、点赞状态、后台阅读量排序等多项功能！DUX主题7.4版本适用于垂直站点、科技博客、个人站，扁平化设计、简洁白色、超多功能配置、会员中心、直达链接、自动缩略图！ DUX...

zhangxiangliang 2021-09-09 11:53 评论0 收藏0
Redis在Php项目中的实际应用场景

摘要：前言一些案例中有的同学说为什么不可以用类型，类型完全可以实现呀我建议你看下我的专栏文章高级用法里面介绍了用类型的好处商品维度计数对商品喜欢数，评论数，鉴定数，浏览数进行计数说起电商，肯定离不开商品，而附带商品有各种计数喜欢数，评论数，鉴定数前言一些案例中有的同学说为什么不可以用string类型，string类型完全可以实现呀我建议你看下我的专栏文章《Redis高级用法》,里面介...

Blackjun 2019-06-27 13:45 评论0 收藏0
JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序

摘要：之所以把计数排序桶排序基数排序放在一起比较，是因为它们的平均时间复杂度都为。动画计数排序思想找出待排序的数组中最大和最小的元素。桶排序计数排序能派上用场吗手机号码有位，范围太大，显然不适合用这两种排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者...

Awbeci 2019-08-26 10:24 评论0 收藏0