CSP-J算法基础 计数排序
文章目录
- 前言
- 计数排序
- 计数排序的过程
- 总结
- 代码实现计数排序
- 总结
前言
计数排序
计数排序(Counting Sort)是一种线性时间复杂度的排序算法,适用于范围有限的整数排序。它通过计数每个值出现的次数,依次排列这些值。该算法不通过比较元素大小进行排序,而是根据值的分布情况完成排序。
计数排序的过程
假设我们有一个数组 [4, 2, 2, 8, 3, 3, 1],需要对它进行升序排序。
-
初始数组:
[4, 2, 2, 8, 3, 3, 1] -
找到最大值和最小值:
计数数组大小的公式是:

其中:
- 最大值 是输入数组中的最大元素;
- 最小值 是输入数组中的最小元素;
- 加上 1 是为了包括最大值和最小值之间的所有可能值。
这个公式确保计数数组有足够的空间来记录所有输入数组中可能的整数值的出现次数。
- 最大值是
8,最小值是1。因此,计数数组的大小为8 - 1 + 1 = 8。
-
构建计数数组:
- 创建一个大小为
8的计数数组count,初始时所有值为0。即:
[0, 0, 0, 0, 0, 0, 0, 0]
- 创建一个大小为
-
计算每个元素出现的次数:
- 遍历输入数组,并增加计数数组对应位置的值:
- 数字
4:count[4 - 1]++,count变为[0, 0, 0, 1, 0, 0, 0, 0] - 数字
2:count[2 - 1]++,count变为[0, 1, 0, 1, 0, 0, 0, 0] - 数字
2:count[2 - 1]++,count变为[0, 2, 0, 1, 0, 0, 0, 0] - 数字
8:count[8 - 1]++,count变为[0, 2, 0, 1, 0, 0, 0, 1] - 数字
3:count[3 - 1]++,count变为[0, 2, 1, 1, 0, 0, 0, 1] - 数字
3:count[3 - 1]++,count变为[0, 2, 2, 1, 0, 0, 0, 1] - 数字
1:count[1 - 1]++,count变为[1, 2, 2, 1, 0, 0, 0, 1]
- 数字
现在,计数数组显示了输入数组中每个元素出现的次数:
[1, 2, 2, 1, 0, 0, 0, 1] - 遍历输入数组,并增加计数数组对应位置的值:
-
累加计数数组:
- 修改计数数组,使其变成累计计数数组。这表示每个数字应当出现在最终数组中的位置:
count[1] = count[0] + count[1]→[1, 3, 2, 1, 0, 0, 0, 1]count[2] = count[1] + count[2]→[1, 3, 5, 1, 0, 0, 0, 1]count[3] = count[2] + count[3]→[1, 3, 5, 6, 0, 0, 0, 1]count[4] = count[3] + count[4]→[1, 3, 5, 6, 6, 0, 0, 1]count[5] = count[4] + count[5]→[1, 3, 5, 6, 6, 6, 0, 1]count[6] = count[5] + count[6]→[1, 3, 5, 6, 6, 6, 6, 1]count[7] = count[6] + count[7]→[1, 3, 5, 6, 6, 6, 6, 7]
累加后的计数数组为:
[1, 3, 5, 6, 6, 6, 6, 7] - 修改计数数组,使其变成累计计数数组。这表示每个数字应当出现在最终数组中的位置:
-
构建排序后的数组:
- 使用计数数组将输入数组中的每个元素放到正确的位置:
- 数字
1:count[1 - 1]--,将1放入排序后的数组第0位。数组变为[1, _, _, _, _, _, _] - 数字
2:count[2 - 1]--,将2放入排序后的数组第2位。数组变为[1, _, 2, _, _, _, _] - 数字
2:count[2 - 1]--,将2放入排序后的数组第1位。数组变为[1, 2, 2, _, _, _, _] - 数字
3:count[3 - 1]--,将3放入排序后的数组第4位。数组变为[1, 2, 2, _, 3, _, _] - 数字
3:count[3 - 1]--,将3放入排序后的数组第3位。数组变为[1, 2, 2, 3, 3, _, _] - 数字
4:count[4 - 1]--,将4放入排序后的数组第5位。数组变为[1, 2, 2, 3, 3, 4, _] - 数字
8:count[8 - 1]--,将8放入排序后的数组第6位。数组变为[1, 2, 2, 3, 3, 4, 8]
- 数字
- 使用计数数组将输入数组中的每个元素放到正确的位置:
-
最终结果:
- 输入数组
[4, 2, 2, 8, 3, 3, 1]被排序为[1, 2, 2, 3, 3, 4, 8]。
- 输入数组
总结
计数排序通过创建一个计数数组来记录每个元素出现的次数,然后使用这些计数信息将元素放置在正确的位置。这个算法的时间复杂度是 O(n+k),其中 n 是输入数据的大小,k 是数据的取值范围。对于元素范围较小且数据量大的情况,计数排序表现非常出色。然而,当数据范围较大时,计数排序的空间复杂度较高,使用效果可能不理想。
代码实现计数排序
#include <stdio.h>
#include <stdlib.h>// 计数排序函数
void countingSort(int arr[], int n) {int i, max = arr[0], min = arr[0];// 找到数组中的最大值和最小值for (i = 1; i < n; i++) {if (arr[i] > max) {max = arr[i];}if (arr[i] < min) {min = arr[i];}}printf("最大值: %d, 最小值: %d\n", max, min);// 计算计数数组的大小int range = max - min + 1;int *count = (int *)calloc(range, sizeof(int)); // 动态分配内存并初始化为0// 计算每个元素出现的次数for (i = 0; i < n; i++) {count[arr[i] - min]++;}// 打印计数数组printf("计数数组:\n");for (i = 0; i < range; i++) {printf("%d ", count[i]);}printf("\n");// 将计数数组累加,调整为位置索引for (i = 1; i < range; i++) {count[i] += count[i - 1];}// 打印累加后的计数数组printf("累加后的计数数组:\n");for (i = 0; i < range; i++) {printf("%d ", count[i]);}printf("\n");// 创建输出数组int *output = (int *)malloc(n * sizeof(int));// 按照计数数组的值,构建排序后的数组//从后向前遍历排序 for (i = n - 1; i >= 0; i--) {output[count[arr[i] - min] - 1] = arr[i];count[arr[i] - min]--; // 更新计数数组}// 打印排序后的数组printf("排序后的数组:\n");for (i = 0; i < n; i++) {arr[i] = output[i];printf("%d ", arr[i]);}printf("\n");// 释放动态分配的内存free(count);free(output);
}int main() {int arr[] = {5, 2, 2, 8, 3, 3, 1};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组:\n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");// 调用计数排序countingSort(arr, n);return 0;
}
总结
相关文章:
CSP-J算法基础 计数排序
文章目录 前言计数排序计数排序的过程总结 代码实现计数排序总结 前言 计数排序 计数排序(Counting Sort)是一种线性时间复杂度的排序算法,适用于范围有限的整数排序。它通过计数每个值出现的次数,依次排列这些值。该算法不通过比…...
Java泛型类型解析
解析泛型类型 获取字段泛型类型 **java.lang.reflect.Field#getGenericType**: 作用:返回字段的泛型类型。返回类型:Type。如果字段是一个泛型类型,这个方法将返回一个表示这个泛型类型的 Type 对象,比如 ParameterizedType&…...
EasyExcel 学习之 导出 “类型及精度问题”
目录 现象缘由类型问题精度/格式问题精度问题格式问题 解决 现象 Excel 导出时,可能面临几个问题: 类型问题:常见类型转换、URL 转图片等精度/格式问题:数字、日期转换 缘由 类型问题 Excel 常见的 API 有两种,Ea…...
从视频中每隔10帧截取一帧并保存为图片
要从视频中每隔10帧截取一帧并保存为图片,可以使用 OpenCV 库。 import cv2# 视频文件的路径 video_path path/to/your/video.mp4# 创建一个 VideoCapture 对象 cap cv2.VideoCapture(video_path)# 检查是否成功打开视频文件 if not cap.isOpened():print("E…...
防火墙、firewalld指令、更改yum源为阿里云的yum源及常见问题
一、防火墙分类 1、硬件防火墙 2、软件防火墙(咱们昨天学的就属于这个) 3、waf 4、下一代防火墙 二、工作原理 1、通过对进出口数据的(数据、端口、IP等)进行过滤,达到对内网数据的保护。 2、防护危险的一堵墙、…...
5G Multicast/Broadcast Services(MBS) (二) Multicast
这篇是Multicast handling的overview,正文开始。 值得注意的是,对于5MBS multicast,UE只有处于 RRC connected和Inactive时,网络侧才可以 通过MRB将MBS multicast数据传输到 UE;处于Idle态只能进行MBS broadcast过程。 对于multicast涉及的RN...
【计算机方向】中科院二区潜力刊!最快14天accept,还是非OA ,不能错过!
期刊解析 🚩本 期 期 刊 看 点 🚩 非OA 审稿友好,审稿速度快 自引率7.9% 今天小编带来计算机领域SCI快刊的解读! 如有相关领域作者有意投稿,可作为重点关注! 01 期刊信息✦ 期刊名称:Inter…...
合适做项目交付的物联网平台:ThingsKit
ThingsKit,作为一个专为项目交付设计的物联网平台,凭借其强大的功能和灵活性,成为了众多企业的首选。 一、ThingsKit的核心优势 模块化设计:ThingsKit采用模块化设计,使得用户可以根据自己的需求灵活选择和组合不同的…...
python绘制3D瀑布图
成品: 代码: def line_3d(x, y, z, x_label_indexs):"""在y轴的每个点,向x轴的方向延伸出一个折线面:展示每个变量的时序变化。x: x轴,时间维,右边。y: y轴,变量维,…...
ArcGIS中怎么合并多个点图层并删除重复点?
最近,我接到了一个怎么合并多个点图层并删除其中的重复点的咨询。 下面是我对这个问题的解决思路: 1、合并图层 在地理处理工具里面 选择合并 并设置好要合并的图层即可 2、接下来在 数据管理工具→常规→删除相同项 即可 希望这些建议能对大家有所帮…...
【vue、UI】使用 Vue2 和 Element UI 封装 CSV 文件上传组件,实现csv回显
文章目录 前言组件功能概述实现效果组件模板结构组件的核心逻辑1.数据属性定义2.方法拆解3.CSV 文件解析方法4. 错误处理方法 组件样式完整组件代码总结待优化的地方 前言 在 Vue2 项目中,我们经常需要封装一些可重用的组件来提升开发效率。本文将介绍如何使用 Vue…...
erlang学习: Mnesia Erlang数据库2
Mnesia数据库增加与查询学习 -module(test_mnesia).-record(shop, {item, quantity, cost}). -record(cost, {name, price}). -record(design, {info, plan}). %% API -export([insert/3,select/1,start/0]). start() ->mnesia:start().insert(Name, Quantity, Cost) ->…...
电脑文件怎么备份?推荐6个高效便捷的文件备份的方法
在日常使用电脑的过程中,数据备份是一项至关重要的任务。无论是个人用户还是企业用户,都需要确保重要文件的安全性和可恢复性。 以下是推荐的六个高效便捷的文件备份方法,帮助你轻松守住你的文档安全。 1. 使用USB存储设备 USB存储设备如U盘…...
Procdump抓ToDesk密码
目录 前言 1.工具教程 2.转储数据 3.密码获取 4.总结 前言 本文是因为在公众号上看到一篇文章随想着实战中利用ToDesk秀操作失败后,实验环境成功复现后写下。ProcDump[1] 是一个命令行实用工具,其主要用途是监视应用程序的 CPU 峰值,并在…...
ESP8266下载固件→连接阿里云
一、工具准备 1、ESP8266Wifi模块 2、ESP8266下载器 ESP8266-01模块 二、固件配置 CH340串口工具-烧录ESP8266-01固件_esp8266 ch340烧录-CSDN博客文章浏览阅读444次,点赞6次,收藏3次。CH340会有供电不足的问题,因此需要外部供电_esp…...
20240911软考架构-------软考156-160答案解析
每日打卡题156-160答案 156、NoSQL整体框架分为4层,由下至上分为数据持久层、数据分布层、数据逻辑模型层和(1)。(2)定义了数据的存储形式。(3)定义了数据是如何分布的。(4…...
工厂模式与策略模式(golang示例)
一、工厂模式简介 工厂模式是一种创建型设计模式,主要用于封装对象的创建过程。通过使用工厂模式,客户端代码无需直接实例化对象,而是通过工厂类来创建对象。这样可以将对象的创建与使用分离,从而提高代码的灵活性。 1.1 工厂模…...
批量视频如何做成一个二维码(分步骤教程)
原创教程,阿酷TONY,2024.9.11,湖南长沙 批量视频如何做成一个二维码(分步骤教程),场景应用: 1. 一批视频需要按组分类,生成一个二维码,实现扫一个二维码,观看…...
OpengGL教程(三)---使用VAO和VBO方式绘制三角形
本章参考官方教程:learnopengl-cn VertexShader.glsl #version 330 core layout(location 0) in vec3 position; layout(location 1) in vec3 color; uniform mat4 projection; // 投影矩阵 out vec4 ourColor; void main() {gl_Position projection * vec4(p…...
【单片机开发】单片机常用开发工具
【前言】 在嵌入式系统领域,单片机(Microcontroller, MCU)作为核心组件,广泛应用于智能家居、工业控制、汽车电子等众多领域。而单片机开发工具,则是开发者们实现创意、解决问题的重要助手。本文主要讲述目前主流的单…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
