计数排序.
一.定义:
计数排序(Counting Sort)是一种非比较性质的排序算法,其时间复杂度为O(n+k)(其中n为待排序的元素个数,k为不同值的个数)。这意味着在数据值范围不大并且离散分布的情况下,规模越大,排序速度越快的特点。然而,如果数列元素不满足整数和有确定范围的条件,则不能使用计数排序。
二.原始代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>// 计数排序
void count_sort(int num[], int len) {// 寻找最大值int max = num[0];for (int i = 1; i < len; i++) {max = max > num[i] ? max : num[i]; // 更新最大值}int range = max + 1; // 计数数组的长度为最大值加1int *arr = (int *)malloc(sizeof(int) * range); // 申请空间memset(arr, 0, sizeof(int) * range); // 初始化计数数组为0for (int i = 0; i < len; i++) {arr[num[i]]++; // 对每个元素进行计数}// 填充原数组int j = 0;for (int i = 0; i < range; i++) {while (arr[i] != 0) { // 将计数数组中的每个非零元素放回原数组num[j] = i; // 填充元素arr[i]--; // 计数减一j++; // 标记原数组填充到的位置}}free(arr); // 释放计数数组空间
}int main() {int num[12] = { 5, 8, 5, 4, 6, 8, 9, 7, 2, 3, 4, 5 };count_sort(num, 12); // 执行计数排序// 打印结果for (int i = 0; i < 12; i++){printf("%d ", num[i]);}return 0;
}
输出结果:
2 3 4 4 5 5 5 6 7 8 8 9
代码优点:
- 计数排序是一个非比较排序算法,对于一个给定的输入数组,不论数组中的数字如何分布,其时间复杂度始终稳定在O(n)。
- 擅长处理小范围大量重复的整数数据,效率非常高,实际运行速度通常比其他的O(n log n)比较类排序算法要快。
代码缺点:
- 计数排序算法只能用来排序整数,并且只能处理非负整数,对于负整数和小数,此算法无法正常工作,需要进行额外处理才能排序。
- 该排序算法需要额外的空间来存储计数数组,如果输入数据的范围(最大值-最小值)过大,将会导致空间的大量浪费。
- 如果待排序的数列中最大和最小数值的差过大,需要很大的辅助空间,因此空间复杂度显著上升,空间效率低。
- 计数排序是一种不稳定的排序,无法保证相同数值的元素在排序后保持原有的顺序。
三.优化代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>// 计数排序函数
void count_sort(int num[], int len) {int max = num[0]; // 初始化最大值为数组第一个元素int min = num[0]; // 初始化最小值为数组第一个元素// 找出数组中最大值和最小值for (int i = 1; i < len; i++) {max = max > num[i] ? max : num[i];min = min < num[i] ? min : num[i];}int range = max - min + 1; // 计算最大值与最小值的差值和1(确定结果数组的大小)// 动态分配range大小的计数数组,并初始化为0int *arr = (int *)malloc(sizeof(int) * range);memset(arr, 0, sizeof(int) * range); // 计算每个元素出现的次数for (int i = 0; i < len; i++) {arr[num[i]-min]++; // 使用当前元素值减去最小值作为索引}// 按升序排列原数组for (int i = 0, t = 0; i < range; i++) {while (arr[i] != 0) {num[t] = i + min; // 使用当前索引加上最小值得到原始值t++;arr[i]--; // 减去一个元素的计数}}// 释放动态分配的计数数组空间free(arr);
}int main() {// 待排序的数组int num[10] = { -10, 10, -9, 9, 8, 7, 7, 6, 6, 6 };// 使用计数排序算法进行排序count_sort(num, 10);// 输出排序后的数组元素for (int i = 0; i < 10; i++) {printf("%d ", num[i]);}return 0;
}
优化点:
1.可以实现包含负数的数组排序
相关文章:
计数排序.
一.定义: 计数排序(Counting Sort)是一种非比较性质的排序算法,其时间复杂度为O(nk)(其中n为待排序的元素个数,k为不同值的个数)。这意味着在数据值范围不大并且离散分布的情况下,规…...
flink中配置Rockdb的重要配置项
背景 由于我们在flink中使用了状态比较大,无法完全把状态数据存放到tm的堆内存中,所以我们选择了把状态存放到rockdb上,也就是使用rockdb作为状态后端存储,本文就是简单记录下使用rockdb状态后端存储的几个重要的配置项 使用rockdb状态后端…...
代码随想录二刷 | 数组 | 有序数组的平方
代码随想录二刷 | 数组 | 有序数组的平方 题目描述题目分析 & 代码实现暴力排序双指针法 题目描述 977.有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 …...
基于单片机C51全自动洗衣机仿真设计
**单片机设计介绍, 基于单片机C51全自动洗衣机仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机C51的全自动洗衣机仿真设计是一个复杂的项目,它涉及到硬件和软件的设计和实现。以下是对这…...
「Verilog学习笔记」实现3-8译码器①
专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点,刷题网站用的是牛客网 分析 ① 本题要求根据38译码器的功能表实现该电路,同时要求采用基础逻辑门实现,那么就需要将功能表转换为逻辑表达式。 timescale 1ns/1nsmodule d…...
Centos(Linux)服务器安装Dotnet8 及 常见问题解决
1. 下载dotnet8 sdk 下载 .NET 8.0 SDK (v8.0.100) - Linux x64 Binaries 拿到 dotnet-sdk-8.0.100-linux-x64.tar.gz 文件 2. 把文件上传到 /usr/local/software 目录 mkdir -p /usr/local/software/dotnet8 把文件拷贝过去 mv dotnet-sdk-8.0.100-linux-x64.tar.gz /usr/loc…...
最强人工智能ChatGPT引领AIGC发展
从公众号转载,关注微信公众号掌握更多技术动态 --------------------------------------------------------------- ——AI不会淘汰所有人,但会淘汰不懂AI的人 一、最强人工智能GPT-4 Turbo 在前不久的OpenAI开发者大会,正值Chatgpt3.5发布一…...
10.Oracle的同义词与序列
oracle11g的同义词与序列 一、Oracle同义词:1、同义词的基本使用2、同义词的相关权限3、同义词的作用范围 二、Oracle序列:1、序列的基本操作2、序列的相关权限 一、Oracle同义词: 同义词是一个数据库对象的别名,它允许用户通过不…...
【周报2023-11-10】
周报2023-11-10 本周的主要工作下周工作计划 本周的主要工作 本周的主要工作就有三个 第一个是进行对我们目前的高企项目的完善情况第二个是对于高企项目的接口对接情况以及细节的把控第三个为新的小程序项目做准备工作 首先第一个高企项目的完善情况得话主要是页面上 对于原…...
搜维尔科技:业内普遍选择Varjo头显作为医疗VR/AR/XR解决方案
Varjo 的人眼分辨率混合现实和虚拟现实头显将医疗专业人员的注意力和情感投入提升到更高水平。借助逼真的 XR/VR,医疗和保健人员可以为最具挑战性的现实场景做好准备! 在虚拟、增强和混合现实中进行最高水平的训练和表现 以逼真的 3D 方式可视化医疗数据…...
数据结构02附录01:顺序表考研习题[C++]
图源:文心一言 考研笔记整理~🥝🥝 之前的博文链接在此:数据结构02:线性表[顺序表链表]_线性链表-CSDN博客~🥝🥝 本篇作为线性表的代码补充,每道题提供了优解和暴力解算法…...
ClientDateSet:Cannot perform this operation on a closed dataset
一、问题表现 Delphi 三层DataSnap,使用AlphaControls控件优化界面,一窗口编辑时,出现下列错误提示: 编译通过,该窗口中,重新显示数据,下图: 相关代码: procedure…...
python中列表的基础解释
列表: 一种可以存放多种类型数据的数据结构 列表的创建: 1.用【】创建列表 #创建一个空列表 list1[] #创建一个非空列表 list2 [zhang,li,ying,1,2,3] #输出内容及类型 print(list1,type(list1)) print(list2,type(list2))结果: 2.使用list…...
『力扣刷题本』:链表分割
一、题目 现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。 二、思路解析 首先,让我们列出我们需要做的事情&…...
FISCOBCOS入门(十)Truffle测试helloworld智能合约
本文带你从零开始搭建truffle以及编写迁移脚本和测试文件,并对测试文件的代码进行解释,让你更深入的理解truffle测试智能合约的原理,制作不易,望一键三连 在windos终端内安装truffle npm install -g truffle 安装truffle时可能出现网络报错,多试几次即可 truffle --vers…...
Unity Text文本首行缩进两个字符的方法
Text文本首行缩进两个字符的方法比较简单。通过代码把"\u3000\u3000"加到文本字符串前面即可。 参考如下代码: TMPtext1.text "\u3000\u3000" "这是一段有首行缩进的文本内容。\n这是第二行"; 运行效果如下图所示: 虽…...
TS的函数重载、类型合并、类型断言
函数重载 let list5 [1, 2, 3, 4]function findNum(id: number): number[]function findNum(): number[]function findNum(list: number[]): number[]function findNum(ids?: number | number[]): number[] {if (typeof ids number) {return list5.filter((num) > num …...
JVM:字节码文件,类的生命周期,类加载器
JVM:字节码文件,类的生命周期,类加载器 为什么要学这门课程 1. 初识JVM1.1. 什么是JVM1.2. JVM的功能1.3. 常见的JVM 2. 字节码文件详解2.1. Java虚拟机的组成2.2. 字节码文件的组成2.2.1. 以正确的姿势打开文…...
【IPC】消息队列
1、IPC对象 除了最原始的进程间通信方式信号、无名管道和有名管道外,还有三种进程间通信方式,这 三种方式称之为IPC对象 IPC对象分类:消息队列、共享内存、信号量(信号灯集) IPC对象也是在内核空间开辟区域,每一种IPC对象创建好…...
内网穿透工具NPS(保姆级教程)
前言: 有时候我们受限于硬件设备和网络的的问题,无法将内网的大容量、高性能存储设备或计算设备对外访问。这个时候就会变的特别苦恼,上云呢成本太大,不用云呢公网又无法直接访问,这个时候怎么办呢,NPS它来…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
