当前位置: 首页 > news >正文

计数排序算法

计数排序

计数排序说明:

计数排序(Counting Sort)是一种非比较性的排序算法,它通过统计元素出现的次数,然后根据元素出现的次数将元素排列在正确的位置上,从而实现排序。计数排序适用于非负整数或者具有确定范围的元素排序,其核心思想是利用一个辅助的计数数组来统计元素出现的次数,并根据次数将元素放置到正确的位置。

以下是计数排序的详细算法原理:

  1. 找到最大值:首先,我们需要遍历待排序的数组,找到其中的最大值,假设最大值为 k。
  2. 创建计数数组:接下来,我们创建一个长度为 k+1 的计数数组 count,并将数组中所有元素初始化为 0。计数数组的索引范围是 0 到 k,每个索引对应一个待排序元素的值。
  3. 统计元素出现次数:遍历待排序的数组,统计每个元素出现的次数,并将统计结果存储在计数数组 count 中。例如,如果数组中有两个元素的值都是 3,那么 count[3] 的值将变为 2。
  4. 计算累加次数:遍历计数数组 count,计算每个元素在排序后的数组中的累加次数。累加次数表示小于或等于当前元素值的元素个数。具体计算方法是通过累加前一个元素的次数得到当前元素的累加次数。这样,count[i] 就表示在排序后的数组中,小于或等于元素 i 的元素个数。
  5. 排序:创建一个与待排序数组相同长度的临时数组 sortedArr,用于存储排序结果。然后,遍历待排序数组,根据计数数组 count 中对应元素的累加次数,将每个元素放到正确的位置上。具体做法是找到当前元素在排序后数组中的索引位置,将其放入 sortedArr 数组的相应位置。同时,更新计数数组 count 中对应元素的累加次数,使其减少 1。这样,相同元素的相对顺序会保持不变。
  6. 完成排序:当遍历完待排序数组后,sortedArr 中就存储了排好序的结果。

计数排序是一种稳定的排序算法,因为相同元素的相对顺序不会改变。它适用于非负整数或者具有确定范围的元素排序,且时间复杂度为 O(n + k),其中 n 是元素个数,k 是待排序元素的最大值。

图解演示:

在这里插入图片描述

当使用计数排序时,需要注意以下几点情况:
  1. 计数排序适用于非负整数或者具有确定范围的元素排序。如果待排序的元素包含负数,计数排序不适用。
  2. 计数排序的时间复杂度为 O(n + k),其中 n 是元素个数,k 是待排序元素的最大值。当元素个数 n 较大,且最大值 k 较小时,计数排序是一个高效的排序算法。但如果 k 过大,导致计数数组非常庞大,可能会造成内存的浪费。
  3. 计数排序是稳定的排序算法,相同元素的相对顺序在排序后保持不变
下面是使用 Go 语言实现计数排序的代码示例:
package mainimport "fmt"func countingSort(arr []int) []int {// 找到最大值,确定计数数组的长度max := arr[0]for _, num := range arr {if num > max {max = num}}// 创建计数数组并统计元素出现次数count := make([]int, max+1)sortedArr := make([]int, len(arr))for _, num := range arr {count[num]++}// 计算累加次数for i := 1; i <= max; i++ {count[i] += count[i-1]}// 排序并构建 sortedArrfor i := len(arr) - 1; i >= 0; i-- {sortedArr[count[arr[i]]-1] = arr[i]count[arr[i]]--}return sortedArr
}func main() {arr := []int{4, 2, 2, 8, 3, 3, 1}fmt.Println("Unsorted array:", arr)arr = countingSort(arr)fmt.Println("Sorted array:", arr)
}

在这个示例中,我们使用计数排序对列表 [4, 2, 2, 8, 3, 3, 1] 进行排序。根据元素范围较小(最大值为 8)且元素均为非负整数,计数排序是一个合适的选择。

总的来说,计数排序适用于非负整数或具有确定范围的元素排序,且适用于元素范围较小、均匀分布的情况。如果待排序元素范围较大或者元素分布不均匀,计数排序可能不是最优选择。在实际使用时,应根据数据的特点来选择合适的排序算法。

相关文章:

计数排序算法

计数排序 计数排序说明&#xff1a; 计数排序&#xff08;Counting Sort&#xff09;是一种非比较性的排序算法&#xff0c;它通过统计元素出现的次数&#xff0c;然后根据元素出现的次数将元素排列在正确的位置上&#xff0c;从而实现排序。计数排序适用于非负整数或者具有确…...

企业高性能web服务器-nginx

1.nginx简介&#xff1a; nginx是企业高可用的web服务器&#xff0c;nginx也可用来做反向代理服务器器&#xff0c;具有高并发&#xff0c;占用资源少&#xff0c;功能丰富&#xff0c;也可以作为简单的负载均衡。 nginx在企业中的功能&#xff1a; web服务软件 反向代理服务器…...

GaussDB数据库的元数据及其管理简介

目录 一、前言 二、元数据简介 1、元数据定义 2、元数据分类 3、数据库元数据管理 三、GaussDB数据库的元数据管理 1、GaussDB数据库的元数据管理 2、通过“SQL 系统表/系统视图/系统函数”的方式管理&#xff08;采集&#xff09;元数据 1&#xff09;获取表、视图及…...

合并两个有序链表 LeetCode热题100

题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路 遍历两个链表比较大小&#xff0c;按从小到大添加到链表即可。 代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* List…...

【C++】模拟实现string

目录 &#x1f31e;专栏导读 &#x1f31b;定义string类 &#x1f31b;构造函数 &#x1f31b;拷贝构造函数 &#x1f31b;赋值函数 &#x1f31b;析构函数 &#x1f31b;[]操作符重载 &#x1f31b;c_str、size、capacity函数 &#x1f31b;比较运算符重载 &#…...

AI智慧安监视频监控汇聚平台EasyCVR调用接口出现跨域现象该如何解决?

视频监控汇聚EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等&#xff0c;以及厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等&#xff0c;能对外分发RTSP、RTMP、FLV、HLS、WebRTC等格式的视…...

无人机机巢有哪些,无人机机场/机场的主要分类

随着无人机技术的飞速发展&#xff0c;无人机已经渗透到了物流、农业、救援、公共安全等多个领域。而为了使这些无人机能更加高效、灵活地运行&#xff0c;一个新的概念应运而生&#xff0c;那就是无人机机巢&#xff08;UAV Nest&#xff09;。复亚智能无人机机巢是一种供无人…...

联想存储 HH0305_DE4000H 划分卷组、卷、主机

创建卷组 可使用卷组来创建可供主机访问的一个或多个卷。卷组是具有共同特性&#xff08;如 RAID 级别和容量&#xff09;的卷的容器。 关于本任务 如果拥有容量较大的驱动器且可以在控制器之间分发卷&#xff0c;则为每个卷组创建多个卷可以很好地利用存储容量和保护数据。…...

【Python机器学习】实验08 决策树

文章目录 决策树1 创建数据2 定义香农信息熵3 条件熵4 信息增益5 计算所有特征的信息增益&#xff0c;选择最优最大信息增益的特征返回6 利用ID3算法生成决策树7 利用数据构造一颗决策树Scikit-learn实例决策树分类决策树回归Scikit-learn 的决策树参数决策树调参 实验1 通过sk…...

MySQL的innoDB存储引擎如何解决幻读的问题?

MySQL的innoDB存储引擎如何解决幻读的问题 基本情况 MySQL有四种事务隔离级别&#xff0c;这四种隔离级别代表当存在多个事务并发冲突时&#xff0c;可能出现的脏读、不可重复读、幻读的问题InnoDB 在 RR 的隔离级别下 &#xff0c;解决了幻读的问题幻读是指在同一个事务中&a…...

Web3.0:重新定义互联网的未来

&#x1f497;wei_shuo的个人主页 &#x1f4ab;wei_shuo的学习社区 &#x1f310;Hello World &#xff01; Web3.0&#xff1a;重新定义互联网的未来 Web3.0是指下一代互联网&#xff0c;也称为“分布式互联网”。相比于Web1.0和Web2.0&#xff0c;Web3.0具有更强的去中心化、…...

2023年还能选择前端吗?

前言 在Github2022的 Octoverse年度报告上&#xff0c;稳居最多使用榜首的语言可以看到是JavaScript&#xff0c;作为前端中最为关键的一部分&#xff0c;这说明即使现在&#xff0c;前端这一块仍然是大量的人涌进来&#xff0c;依然是火热&#xff0c;但是&#xff0c;一门语…...

sheetJs / xlsx-js-style 纯前端实现导出 excel 表格及自定义单元格样式

文章目录 一、安装二、创建基础工作表三、设置单元格宽度/高度/隐藏单元格四、分配数字格式五、超链接六、单元格注释七、公式八、合并单元格九、自定义单元格样式十、项目地址 一、安装 xlsx 地址&#xff1a;https://www.npmjs.com/package/xlsxSheetJs 地址&#xff1a;htt…...

Redis 报错 RedisConnectionException: Unable to connect to x.x.x.x:6379

文章目录 Redis报错类型可能解决方案 Redis报错类型 org.springframework.data.redis.connection. spingboot调用redis出错 PoolException: Could not get a resource from the pool; 连接池异常:无法从池中获取资源; nested exception is io.lettuce.core. 嵌套异常 RedisConn…...

Stable Diffusion - 真人照片的高清修复 (StableSR + GFPGAN) 最佳实践

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132032216 GFPGAN (Generative Facial Prior GAN) 算法&#xff0c;用于实现真实世界的盲脸恢复的算法&#xff0c;利用预训练的面部 GAN&#xf…...

细讲一个 TCP 连接能发多少个 HTTP 请求(一)

一道经典的面试题是从 URL 在浏览器被被输入到页面展现的过程中发生了什么&#xff0c;大多数回答都是说请求响应之后 DOM 怎么被构建&#xff0c;被绘制出来。但是你有没有想过&#xff0c;收到的 HTML 如果包含几十个图片标签&#xff0c;这些图片是以什么方式、什么顺序、建…...

了解 CVSS:通用漏洞评分系统的应用

漏洞威胁管理至关重要&#xff0c;因为网络犯罪是一种持续存在的全球风险。网络犯罪分子愿意利用软件中的任何漏洞来访问网络和设备。对使用该软件的软件开发人员和组织的影响可能很严重。用户必须处理攻击的结果&#xff0c;例如赎金或数据盗窃&#xff0c;并且还可能面临法律…...

Xilinx FPGA电源设计与注意事项

1 引言 随着半导体和芯片技术的飞速发展&#xff0c;现在的FPGA集成了越来越多的可配置逻辑资源、各种各样的外部总线接口以及丰富的内部RAM资源&#xff0c;使其在国防、医疗、消费电子等领域得到了越来越广泛的应用。当采用FPGA进行设计电路时&#xff0c;大多数FPGA对上电的…...

前端:地图篇(一)

1、前言 在很多的出行程序中&#xff0c;都会使用到地图这一个功能&#xff0c;在实际的开发中我们也不会去开发一个自己的地图模型。如果自己开发一个地图模型&#xff0c;那么需要投入的成本、人力都是非常巨大的。所以我们很多网站和APP中使用的都是第三方的接口和JS&#…...

刷题笔记 day6

力扣 57 和为s的两个整数 class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> v;int i 0 , j nums.size()-1;while(i < j){if(nums[i] nums[j] > target){--j;}else if(nums[i] nums[j] < target){i…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...