计数排序

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

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

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


*算法描述:

找出待排序的数组中最大和最小的元素;

统计数组中每个值为i的元素出现的次数,存入数组C的第i项;

对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);

反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
function countingSort(arr, maxValue) {

    var bucket = new Array(maxValue + 1),
    sortedIndex = 0,
    arrLen = arr.length,
    bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}
var arr = [4, 3, 3, 2, 3, 4, 5, 6, 3, 5, 6, 4, 6, 5, 2, 1, 2];
console.log(arr);
countingSort(arr,6);
console.log(arr);
相关文章
|
Linux
USRP N320更改主时钟频率及测试
USRP N320更改主时钟频率及测试
227 0
|
XML Java 关系型数据库
springboot 集成 mybatis-plus 代码生成器
本文介绍了如何在Spring Boot项目中集成MyBatis-Plus代码生成器,包括导入相关依赖坐标、配置快速代码生成器以及自定义代码生成器模板的步骤和代码示例,旨在提高开发效率,快速生成Entity、Mapper、Mapper XML、Service、Controller等代码。
springboot 集成 mybatis-plus 代码生成器
|
人工智能 安全 数据安全/隐私保护
移动应用开发的未来趋势与挑战
在数字化时代,移动应用已成为我们生活和工作不可或缺的一部分。随着技术的不断进步,移动应用开发领域也迎来了前所未有的发展机遇和挑战。本文将深入探讨移动应用开发的当前状态、未来趋势以及面临的主要挑战,包括跨平台开发的兴起、人工智能的集成、安全性问题、性能优化、用户体验设计的重要性以及隐私保护法规的影响等方面。通过对这些关键领域的分析,旨在为移动应用开发者提供洞见,帮助他们在不断变化的技术环境中保持竞争力。
125 27
|
前端开发 JavaScript 数据可视化
react的应用
react的应用
173 1
|
JSON 网络协议 算法
Netty实战与调优
Netty实战与调优
218 0
|
Linux
致心爱的Linux云酱:
致心爱的Linux云酱:      ​ 当幸福来敲门,感动不期而至,蓦地发现,快乐竟如此简单。 ​ 从未欢度过“白色情人节”,也未有机会关注过;本该是平凡的一天,却燃起久违的感动。 ​ “以前不懂得珍惜,直到失去后才追悔莫及。
1557 0
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1253 5
|
1天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1274 87