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

【排序篇2】选择排序、计数排序

目录

    • 一、选择排序
    • 二、计数排序

一、选择排序

整体思想:
从数组中选出最小值和最大值放在起始位置,直到排序完成

具体步骤:

  1. 定义两个变量begin和end为下标,指向数组始末
  2. 定义要找的最大值的下标为maxi,最小值的下标为mini,刚开始初始化为begin,因为begin和end会缩小,也就是说找最大和最小的范围为当前begin和end之间的范围
  3. 找到最大值的下标和最小值的下标,然后把最小值与begin位置的值交换,这里要考虑特殊情况,最后再交换最大值和end位置的值
  4. 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,然后待排序的数组只要是出现的元素就在临时空间对应的位置计数,最后从小到大恢复原来的元素重新放入数组,完成排序。
思路:

  1. 在数组中找到最大值max和最小值min
  2. 算出最大与最小之间有多少个数,范围range:max-min+1
  3. 开临时空间大小为range,每个元素初始化为0
  4. 待排序数组的元素减去最小值min即对应临时空间的下标,原数组出现的元素会在临时空间对应的位置计数
  5. 从小到大遍历临时空间数组,只要不为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】选择排序、计数排序

目录 一、选择排序二、计数排序 一、选择排序 整体思想&#xff1a; 从数组中选出最小值和最大值放在起始位置&#xff0c;直到排序完成 具体步骤&#xff1a; 定义两个变量begin和end为下标&#xff0c;指向数组始末定义要找的最大值的下标为maxi&#xff0c;最小值的下标为…...

重生奇迹mu敏弓加点攻略

1. 选择正确的属性点分配 在重生奇迹mu游戏中敏弓的属性点分配非常重要。建议将主要属性点分配在敏捷和力量上这样可以提高敏弓的攻击力和闪避能力。适当加点在体力和魔力上可以提高敏弓的生存能力和技能释放次数。不要忘记适当加点在智力上可以提高敏弓的技能威力和命中率。 …...

用通俗易懂的方式讲解:一文讲透主流大语言模型的技术原理细节

大家好&#xff0c;今天的文章分享三个方面的内容&#xff1a; 1、比较 LLaMA、ChatGLM、Falcon 等大语言模型的细节&#xff1a;tokenizer、位置编码、Layer Normalization、激活函数等。 2、大语言模型的分布式训练技术&#xff1a;数据并行、张量模型并行、流水线并行、3D …...

通过IP地址识别风险用户

随着互联网的迅猛发展&#xff0c;网络安全成为企业和个人关注的焦点之一。识别和防范潜在的风险用户是维护网络安全的关键环节之一。IP数据云将探讨通过IP地址识别风险用户的方法和意义。 IP地址的基本概念&#xff1a;IP地址是互联网上设备的独特标识符&#xff0c;它分为IP…...

汇编和C语言转换

C语言和汇编语言之间有什么区别 C语言和汇编语言之间存在显著的区别,主要体现在以下几个方面: 抽象层次: 汇编语言:更接近硬件的低级语言,通常与特定的处理器或指令集紧密相关。它提供了对处理器指令的直接控制,允许程序员直接操作硬件资源,如寄存器、内存等。 C语言:…...

【IOS】惯性导航详解(包含角度、加速度、修正方式的api分析)

参考文献 iPhone的惯性导航&#xff0c;基于步态。https://www.docin.com/p-811792664.html Inertial Odometry on Handheld Smartphones: https://arxiv.org/pdf/1703.00154.pdf 惯性导航项目相关代码&#xff1a;https://github.com/topics/inertial-navigation-systems use…...

Self-Attention

前置知识&#xff1a;RNN&#xff0c;Attention机制 在一般任务的Encoder-Decoder框架中&#xff0c;输入Source和输出Target内容是不一样的&#xff0c;比如对于英-中机器翻译来说&#xff0c;Source是英文句子&#xff0c;Target是对应的翻译出的中文句子&#xff0c;Attent…...

网络协议与攻击模拟_04ICMP协议与ICMP重定向

ICMP协议是网络层协议&#xff0c; 利用ICMP协议可以实现网络中监听服务和拒绝服务&#xff0c;如 ICMP重定向的攻击。 一、ICMP基本概念 1、ICMP协议 ICMP是Internet控制报文协议&#xff0c;用于在IP主机、路由器之间传递控制消息&#xff0c;控制消息指网络通不通、主机是…...

pytest-mock 数据模拟

文章目录 mock 测试unittest.mockMock类MagicMock类patch装饰器create_autospec函数断言的方法 pytest-mock 使用 mock 测试 在单元测试时&#xff0c;有些数据需要依赖其他服务或者不好获取到&#xff0c;此时需要使用mock来模拟对应的函数、对象等。 mock模拟数据的python…...

单片机原理及应用:定时器/计数器综合应用

本文是《单片机原理及应用》专栏中的最后一篇文章&#xff0c;笔者以编译器的安装配置——51单片机简介——LED和数码管外设——开关和按键控制功能切换——外部中断系统——定时器与计数器为知识大纲&#xff0c;介绍了C语言编程控制51单片机的入门教程。作为收尾&#xff0c;…...

R语言【paleobioDB】——pbdb_intervals():通过参数选择,返回多个地层年代段的基本信息

Package paleobioDB version 0.7.0 paleobioDB 包在2020年已经停止更新&#xff0c;该包依赖PBDB v1 API。 可以选择在Index of /src/contrib/Archive/paleobioDB (r-project.org)下载安装包后&#xff0c;执行本地安装。 Usage pbdb_interval (id, ...) Arguments 参数【..…...

阅读笔记lv.1

阅读笔记 sql中各种 count结论不同存储引擎计算方式区别count() 类型 责任链模式常见场景例子&#xff08;闯关游戏&#xff09; sql中各种 count 结论 innodb count(*) ≈ count(1) > count(主键id) > count(普通索引列) > count(未加索引列)myisam 有专门字段记录…...

小鼠的滚动疲劳仪-转棒实验|ZL-200C小鼠转棒疲劳仪

转棒实验|ZL-200C小鼠转棒疲劳仪用于检测啮齿类动物的运动功能。通过测量动物在滚筒上行走的持续时间&#xff0c;来评定**神经系统*病或损坏以及药物对运动协调功能和疲劳的影响。 疲劳实验中&#xff0c;让小鼠在不停转动的棒上运动&#xff0c;肌肉会很快进入疲劳状态&#…...

平衡搜索二叉树(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 过拟合是所有机器学习&#xff0c;深度学习中可能出现的一个比较严重的问题。具体表现就是&#xff1a;你的模型在训练集上处理的效果非常好&…...

PCL 使用克拉默法则进行四点定球(C++详细过程版)

目录 一、算法原理二、代码实现三、计算结果本文由CSDN点云侠原创,PCL 使用克拉默法则进行四点定球(C++详细过程版),爬虫自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT生成的文章。 一、算法原理 已知空间内不共面的四个点,设其坐标为 A (…...

前端导致浏览器奔溃原因分析

内存泄漏 内存泄漏&#xff08;Memory Leak&#xff09;是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放&#xff0c;造成系统内存的浪费&#xff0c;导致程序运行速度减慢甚至系统崩溃等严重后果。&#xff08;程序某个未使用的变量或者方法&#xff0c;长期占…...

力扣:209.长度最小的子数组

1.题目分析&#xff1a; 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0 。 示例 …...

常见类型的yaml文件如何编写?--kind: Service

基本说明 在 Kubernetes 中&#xff0c;Service 是一种抽象的方式&#xff0c;用于定义一组 Pod 的访问方式和网络服务。Service 提供了一个稳定的网络端点&#xff08;Endpoint&#xff09;&#xff0c;使得其他服务或外部用户可以通过 Service 来访问被管理的 Pod。 负载均…...

linux环境下安装postgresql

PostgreSQL: Linux downloads (Red Hat family)postgresql官网 PostgreSQL: Linux downloads (Red Hat family) 环境&#xff1a; centos7 postgresql14 选择版本 执行启动命令 配置远程连接文件 vi /var/lib/pqsql/14/data/postgresql.conf 这里将listen_addresses值由lo…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

【JavaWeb】Docker项目部署

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

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...