当前位置: 首页 > 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…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...