【排序篇2】选择排序、计数排序
目录
- 一、选择排序
- 二、计数排序
一、选择排序
整体思想:
从数组中选出最小值和最大值放在起始位置,直到排序完成
具体步骤:
- 定义两个变量begin和end为下标,指向数组始末
- 定义要找的最大值的下标为maxi,最小值的下标为mini,刚开始初始化为begin,因为begin和end会缩小,也就是说找最大和最小的范围为当前begin和end之间的范围
- 找到最大值的下标和最小值的下标,然后把最小值与begin位置的值交换,这里要考虑特殊情况,最后再交换最大值和end位置的值
- begin++,end–,缩小范围再重复前面的步骤
图示:

代码:
void SelectSort(int* a, int n)
{//数组的范围int begin = 0, end = n - 1;while (begin < end)//控制范围{// maxi和mini是下标,从begin开始,因为begin会变化int maxi = begin, mini = begin;//找最大元素的下标和最小元素的下标for (int i = begin; i <= end; i++)//注意找的范围{if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}//最小值与begin的位置交换Swap(&a[begin], &a[mini]);//特殊情况,如果maxi与begin重叠,此时最大值的下标在miniif (begin == maxi){maxi = mini;}//最大值与end的位置交换Swap(&a[end], &a[maxi]);//缩小范围++begin;--end;}
}
特性总结:
- 时间复杂度:O(N ^ 2)
- 空间复杂度:O(1)
- 不稳定
二、计数排序
计数排序采用相对映射的思想,开辟一块空间,该空间的范围为待排序的数组的最大值和最小值之差加1,并且每个元素初始化为0,然后待排序的数组只要是出现的元素就在临时空间对应的位置计数,最后从小到大恢复原来的元素重新放入数组,完成排序。
思路:
- 在数组中找到最大值max和最小值min
- 算出最大与最小之间有多少个数,范围range:max-min+1
- 开临时空间大小为range,每个元素初始化为0
- 待排序数组的元素减去最小值min即对应临时空间的下标,原数组出现的元素会在临时空间对应的位置计数
- 从小到大遍历临时空间数组,只要不为0,说明该位置是对应原数组有出现的元素,然后依次重新放入原数组,临时空间的下标加上最小值恢复到原数组的元素的值。
图示:

代码:
void CountSort(int* a, int n)
{//找最大值和最小值int max = a[0], 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;//开空间,每个元素为0,后面要计数int* count = (int*)calloc(range, sizeof(int));if (count == nullptr){perror("calloc fail");exit(-1);}//给出现的元素计数for (int i = 0; i < n; i++){count[a[i] - min]++;}//从小到大重新放入数组,完成排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--)//该位置有元素{a[j++] = i + min;//恢复原来的元素,依次放入数组}}free(count);
}
特性总结:
- 计数排序适用于数据较集中的场景
- 时间复杂度:O(N+range)
- 空间复杂度:O(range)
- 稳定
相关文章:
【排序篇2】选择排序、计数排序
目录 一、选择排序二、计数排序 一、选择排序 整体思想: 从数组中选出最小值和最大值放在起始位置,直到排序完成 具体步骤: 定义两个变量begin和end为下标,指向数组始末定义要找的最大值的下标为maxi,最小值的下标为…...
重生奇迹mu敏弓加点攻略
1. 选择正确的属性点分配 在重生奇迹mu游戏中敏弓的属性点分配非常重要。建议将主要属性点分配在敏捷和力量上这样可以提高敏弓的攻击力和闪避能力。适当加点在体力和魔力上可以提高敏弓的生存能力和技能释放次数。不要忘记适当加点在智力上可以提高敏弓的技能威力和命中率。 …...
用通俗易懂的方式讲解:一文讲透主流大语言模型的技术原理细节
大家好,今天的文章分享三个方面的内容: 1、比较 LLaMA、ChatGLM、Falcon 等大语言模型的细节:tokenizer、位置编码、Layer Normalization、激活函数等。 2、大语言模型的分布式训练技术:数据并行、张量模型并行、流水线并行、3D …...
通过IP地址识别风险用户
随着互联网的迅猛发展,网络安全成为企业和个人关注的焦点之一。识别和防范潜在的风险用户是维护网络安全的关键环节之一。IP数据云将探讨通过IP地址识别风险用户的方法和意义。 IP地址的基本概念:IP地址是互联网上设备的独特标识符,它分为IP…...
汇编和C语言转换
C语言和汇编语言之间有什么区别 C语言和汇编语言之间存在显著的区别,主要体现在以下几个方面: 抽象层次: 汇编语言:更接近硬件的低级语言,通常与特定的处理器或指令集紧密相关。它提供了对处理器指令的直接控制,允许程序员直接操作硬件资源,如寄存器、内存等。 C语言:…...
【IOS】惯性导航详解(包含角度、加速度、修正方式的api分析)
参考文献 iPhone的惯性导航,基于步态。https://www.docin.com/p-811792664.html Inertial Odometry on Handheld Smartphones: https://arxiv.org/pdf/1703.00154.pdf 惯性导航项目相关代码:https://github.com/topics/inertial-navigation-systems use…...
Self-Attention
前置知识:RNN,Attention机制 在一般任务的Encoder-Decoder框架中,输入Source和输出Target内容是不一样的,比如对于英-中机器翻译来说,Source是英文句子,Target是对应的翻译出的中文句子,Attent…...
网络协议与攻击模拟_04ICMP协议与ICMP重定向
ICMP协议是网络层协议, 利用ICMP协议可以实现网络中监听服务和拒绝服务,如 ICMP重定向的攻击。 一、ICMP基本概念 1、ICMP协议 ICMP是Internet控制报文协议,用于在IP主机、路由器之间传递控制消息,控制消息指网络通不通、主机是…...
pytest-mock 数据模拟
文章目录 mock 测试unittest.mockMock类MagicMock类patch装饰器create_autospec函数断言的方法 pytest-mock 使用 mock 测试 在单元测试时,有些数据需要依赖其他服务或者不好获取到,此时需要使用mock来模拟对应的函数、对象等。 mock模拟数据的python…...
单片机原理及应用:定时器/计数器综合应用
本文是《单片机原理及应用》专栏中的最后一篇文章,笔者以编译器的安装配置——51单片机简介——LED和数码管外设——开关和按键控制功能切换——外部中断系统——定时器与计数器为知识大纲,介绍了C语言编程控制51单片机的入门教程。作为收尾,…...
R语言【paleobioDB】——pbdb_intervals():通过参数选择,返回多个地层年代段的基本信息
Package paleobioDB version 0.7.0 paleobioDB 包在2020年已经停止更新,该包依赖PBDB v1 API。 可以选择在Index of /src/contrib/Archive/paleobioDB (r-project.org)下载安装包后,执行本地安装。 Usage pbdb_interval (id, ...) Arguments 参数【..…...
阅读笔记lv.1
阅读笔记 sql中各种 count结论不同存储引擎计算方式区别count() 类型 责任链模式常见场景例子(闯关游戏) sql中各种 count 结论 innodb count(*) ≈ count(1) > count(主键id) > count(普通索引列) > count(未加索引列)myisam 有专门字段记录…...
小鼠的滚动疲劳仪-转棒实验|ZL-200C小鼠转棒疲劳仪
转棒实验|ZL-200C小鼠转棒疲劳仪用于检测啮齿类动物的运动功能。通过测量动物在滚筒上行走的持续时间,来评定**神经系统*病或损坏以及药物对运动协调功能和疲劳的影响。 疲劳实验中,让小鼠在不停转动的棒上运动,肌肉会很快进入疲劳状态&#…...
平衡搜索二叉树(AVL树)
目录 前言 一、AVL树的概念 二、AVL树的定义 三、AVL树的插入 四、AVL树的旋转 4.1、右单旋 4.2、左单旋 4.3、左右双旋 4.4、右左双旋 五、AVL树的验证 5.1、 验证其为二叉搜索树 5.2、 验证其为平衡树 六、AVL树的性能 前言 二叉搜索树虽可以缩短查找的效率&…...
2024年1月12日学习总结
学习目标 完成集中学习的readme 完成联邦学习的代码编写 边学习边总结 学习内容 Introduction to Early Stopping 1、Overfitting 过拟合是所有机器学习,深度学习中可能出现的一个比较严重的问题。具体表现就是:你的模型在训练集上处理的效果非常好&…...
PCL 使用克拉默法则进行四点定球(C++详细过程版)
目录 一、算法原理二、代码实现三、计算结果本文由CSDN点云侠原创,PCL 使用克拉默法则进行四点定球(C++详细过程版),爬虫自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT生成的文章。 一、算法原理 已知空间内不共面的四个点,设其坐标为 A (…...
前端导致浏览器奔溃原因分析
内存泄漏 内存泄漏(Memory Leak)是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放,造成系统内存的浪费,导致程序运行速度减慢甚至系统崩溃等严重后果。(程序某个未使用的变量或者方法,长期占…...
力扣:209.长度最小的子数组
1.题目分析: 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 …...
常见类型的yaml文件如何编写?--kind: Service
基本说明 在 Kubernetes 中,Service 是一种抽象的方式,用于定义一组 Pod 的访问方式和网络服务。Service 提供了一个稳定的网络端点(Endpoint),使得其他服务或外部用户可以通过 Service 来访问被管理的 Pod。 负载均…...
linux环境下安装postgresql
PostgreSQL: Linux downloads (Red Hat family)postgresql官网 PostgreSQL: Linux downloads (Red Hat family) 环境: centos7 postgresql14 选择版本 执行启动命令 配置远程连接文件 vi /var/lib/pqsql/14/data/postgresql.conf 这里将listen_addresses值由lo…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
密码学基础——SM4算法
博客主页:christine-rr-CSDN博客 专栏主页:密码学 📌 【今日更新】📌 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 编辑…...
