【非比较排序】计算排序算法
目录
CountSort计数排序
整体思想
图解分析
代码实现
时间复杂度&优缺分析
CountSort计数排序
计数排序是一种非比较排序,不需要像前面的排序一样去比较。
计数排序的特性总结:
1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
2. 时间复杂度:O(MAX(N,范围))
3. 空间复杂度:O(范围)4. 稳定性:稳定
整体思想
- 思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。
- 1. 统计相同元素出现次数
- 2. 根据统计的结果将序列回收到原来的序列中
Count数组
- Count数组中的元素需要全部初始化为0(calloc就可以满足这个要求)
- Count元素是 计算a数组元素个数出现的次数
- Count数组的下标是a数组元素的范围
- 绝对隐射:范围0~max(a中最大的元素)
- 相对隐射:范围0~max-min <<<<<<<<< min~max
- range = max-min+1(映射0~max-min,个数max-min+1)
整个流程
- 遍历一遍:找到最大值 / 最小值
- 计算出Count数组下标范围并且开辟动态空间
- rangge=max-min+1
- 计数Count[a[i]-min]++ (i++)
- 相对隐射回去
注意tips
- i和j能不能公用❓
- a数组的元素可以是负数吗?
- 除了整型其他类型可以吗?
- 后置--&前置--
- calloc>>>>>>calloc - C++ Reference (cplusplus.com)
- Count的下标表示a的元素的范围
- Count的元素表示a的元素出现的个数(计数)
图解分析


代码实现
void CountSort(int* a, int n)
{//找最大值/最小值/创建的tmp的范围在这个之间int max = a[0];int min = a[0];for (int i = 0; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;//注意int* count = (int*)calloc(range, sizeof(int));//计数for (int j = 0; j < n; j++){count[a[j]-min]++;}//相对隐射回去int i = 0;for (int k = 0; k < range; k++){while (count[k]--){a[i++] = k + min;}}
}
时间复杂度&优缺分析
时间复杂度:O(N)
- 时间复杂度:O(a(N)+coun(N))(count的N是a的数据范围)
- 计数排序不需要比较元素大小
- 优势:效率极高
- 局限性:不适合范围很大,计数排序只适用于整型,不同数据类型的,实践意义不高。(现实实践,更多的是结构体排序,不能适用计数排序)
🙂感谢大家的阅读,若有错误和不足,欢迎指正。下篇总结各个排序。
相关文章:
【非比较排序】计算排序算法
目录 CountSort计数排序 整体思想 图解分析 代码实现 时间复杂度&优缺分析 CountSort计数排序 计数排序是一种非比较排序,不需要像前面的排序一样去比较。 计数排序的特性总结: 1. 计数排序在数据范围集中时,效率很高,但…...
数据结构与算法 - 数组与二分查找 + Leetcode典型题
1. 什么是数组 数组是存放在连续内存空间上的相同类型数据的集合。 数组可以方便的通过下标索引的方式获取到下标下对应的数据。 C中二维数组在地址空间上也是连续的。 需注意: 数组的下标从0开始。数组内存空间的地址是连续的。数组的元素是不能删的,…...
SQL进阶(三):Join 小技巧:提升数据的处理速度
复杂数据结构处理:Join 小技巧:提升数据的处理速度 本文是在原本sql闯关的基础上总结得来,加入了自己的理解以及疑问解答(by GPT4) 原活动链接 用到的数据:链接 提取码:l03e 目录 1. 课前小问…...
开发知识点-.netC#图形用户界面开发之WPF
C#图形用户界面开发 NuGet框架简介WinForms(Windows Forms):WPF(Windows Presentation Foundation):UWP(Universal Windows Platform):MAUI(Multi-platform App UI):选择控件参考文章随笔分类 - WPF入门基础教程系列...
基于springboot实现流浪动物救助网站系统项目【项目源码+论文说明】
基于springboot实现流浪动物救助网站系统演示 摘要 然而随着生活的加快,也使很多潜在的危险日益突显出来,比如在各种地方会发现很多无家可归的、伤痕累累的、可怜兮兮的动物,当碰到这种情况,是否会立马伸出双手去帮助、救助它们&…...
灰度负载均衡和普通负载均衡有什么区别
灰度负载均衡(Gray Load Balancing)与普通负载均衡的主要区别在于它们服务发布和流量管理的方式。 灰度负载均衡 目的:主要用于灰度发布,即逐步向用户发布新版本的服务,以减少新版本可能带来的风险。工作方式&#x…...
【二分查找】朴素二分查找
二分查找 题目描述 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9…...
Windows Docker 部署 Redis
部署 Redis 打开 Docker Desktop,切换到 Linux 内核。然后在 PowerShell 执行下面命令,即可启动一个 redis 服务。这里安装的是 7.2.4 版本,如果需要安装其他或者最新版本,可以到 Docker Hub 中进行查找。 docker run -d --nam…...
什么是VR虚拟现实|虚拟科技博物馆|VR设备购买
虚拟现实(Virtual Reality,简称VR)是一种通过计算机技术模拟出的一种全新的人机交互方式。它可以通过专门的设备(如头戴式显示器)将用户带入一个计算机生成的虚拟环境之中,使用户能够与这个虚拟环境进行交互…...
高性能API云原生网关 APISIX安装与配置指南
Apache APISIX是Apache软件基金会下的顶级项目,由API7.ai开发并捐赠。它是一个高性能的云原生API网关,具有动态、实时等特点。 APISIX网关可作为所有业务的流量入口,为用户提供了丰富的功能,包括动态路由、动态上游、动态证书、A…...
Gradio Dataframe 学习笔记
Gradio Dataframe 学习笔记 0. 简介1. 使用场景2. 测试数据3. 学习代码4. 更多功能5. 学习资源6. 总结 0. 简介 Gradio是一个用于构建交互式机器学习界面的Python库。它可以轻松创建各种类型的界面,包括用于数据可视化和探索的界面。 Gradio Dataframe 组件是 Gra…...
深入理解计算机系统笔记
1.1 嵌套的数组 当我们创建数组的数组时,数组分配和引用的一般原则也是成立的。 例如,声明 int A[5][3]; 等价于下面的声明 typedef int row3_t[3]; row3_t A[5] 要访问多维数组的元素,编译器会以数组起始为基地址, (可能需…...
300分钟吃透分布式缓存(拉钩教育总结)
开篇寄语 开篇寄语:缓存,你真的用对了吗? 你好,我是你的缓存老师陈波,可能大家对我的网名 fishermen 会更熟悉。 我是资深老码农一枚,经历了新浪微博从起步到当前月活数亿用户的大型互联网系统的技术演进…...
2024亚马逊全球开店注册前需要准备什么?
在2023年出海四小龙SHEIN、Temu、速卖通AliExpress、TikTok Shop快速增长扩张,成为了中国跨境卖家“逃离亚马逊”的新选择。但是,跨境电商看亚马逊。当前,亚马逊仍然是跨境电商行业的绝对老大,占有将近70%成以上的业务份额。 作为…...
android Service 与 activity 通信 并不断传数据
注:这只是个Demo 以下载为案例,实现开启下载,暂停下载,下载进度不断发送给activity class DownloadService : Service() {override fun onBind(intent: Intent?): IBinder? {return MyBinder()}inner class MyBinder : Binder…...
Acwing-基础算法课笔记之数学知识(扩展欧几里得算法)
Acwing-基础算法课笔记之数学知识(扩展欧几里得算法) 一、扩展欧几里得算法1、裴蜀定理2、过程模拟3、代码模板 二、线性同余方程1、定义2、模拟过程3、结论证明 一、扩展欧几里得算法 1、裴蜀定理 对于任意正整数 a a a, b b b࿰…...
简单排列组合题(python版)
文章预览: 题目解法一输出结果 解法二输出结果输出结果 题目 有四个数字:1,2,3,4能组成多少个互不相同且无重复的数字的三位数? 各式多少? 解法一 我们粗略看一下这个题既然我们要组成三位数,那我们就循环3层每一层出一个数,并且if语句判…...
【排坑】搭建 Karmada 环境
git clone 报错 问题:Failed to connect to github.com port 443:connection timed out 解决: git config --global --unset http.proxy【hack/local-up-karmada.sh】 1. karmada ca-certificates (no such package) 问题:fetching http…...
每日一类:Qt GUI开发的基石《QWidget》
深入探索QWidget:Qt GUI开发的基石 在Qt框架中,QWidget类扮演着构建图形用户界面(GUI)的基础角色。它不仅提供了窗口的基本功能,还允许开发者通过继承和定制来创建各式各样的用户界面元素。本文将详细介绍QWidget的关…...
人大金仓与mysql的差异与替换
人大金仓中不能使用~下面的符号,字段中使用”,无法识别建表语句 创建表时语句中只定义字段名.字段类型.是否是否为空 Varchar类型改为varchar(长度 char) Int(0) 类型为int4 定义主键:CONSTRAINT 键名 主键类型&#x…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)
名人说:莫道桑榆晚,为霞尚满天。——刘禹锡(刘梦得,诗豪) 原创笔记:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 上一篇:《数据结构第4章 数组和广义表》…...
Canal环境搭建并实现和ES数据同步
作者:田超凡 日期:2025年6月7日 Canal安装,启动端口11111、8082: 安装canal-deployer服务端: https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...


