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

【数据结构】选择排序——选择排序 和 堆排序

选择排序 和 堆排序

  • 一、选择排序
    • 选择排序的思路及其代码
    • 选择排序的弊端
  • 二、堆排序
  • 三、速度对比
    • 同时排10000个数
    • 同时排100000个数
    • 同时拍500000个数
    • 堆排 1 亿个数

一、选择排序

选择排序的思路及其代码

选择排序思路很简单
就是经过将数组遍历选择最小值
将最小值位置的数与数组最前面位置的数进行交换
如此反复,完成排序
在这里插入图片描述

为了提高效率我们在一次遍历过程中同时找最大和最小值
代码如下:

//选择排序
void SelectSort(int* a, int n)
{int maxi = n - 1;int mini = 0;while (mini < maxi){//找出最大最小值的下标int max = maxi;int min = mini;for (int i = mini; i <= maxi; i++){if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}//将最大最小值进行更新,将最大最小值放到数组两边Swap(&a[mini], &a[min]);//若最大值在原最小值的位置,将位置更新if (max == mini){max = min;}Swap(&a[maxi], &a[max]);maxi--;mini++;}
}

运行结果:
在这里插入图片描述

选择排序的弊端

因为无论数组中原数组是如何排列
选择排序都要遍历数组
所以它的最好与最坏的情况下
时间复杂度都是 O(N ^ 2)
效率低下,正常情况下是不会使用这个排序的

二、堆排序

以下的链接又对堆和堆排序的讲解:
堆以及堆排序

下面我就直接把代码贴出来:

//向下调整(建大堆)
void AdjustDown(int* a, int parent, int n)
{//左孩子int child = parent * 2 + 1;while (child + 1 < n){//先找左右孩子中大的一个if (child + 1 < n && a[child] < a[child + 1]){child++;}//将父亲节点与孩子节点进行比较,将大的移到父亲节点if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, i, n);}//进行堆排序int size = n - 1;while (size > 0){//先将堆的第一个数与最后一个数交换Swap(&a[0], &a[size--]);//向下调整AdjustDown(a, 0, size);}
}

运行结果:
在这里插入图片描述
堆排序的时间复杂度为 O(N * logN)

三、速度对比

同时排10000个数

在这里插入图片描述

同时排100000个数

在这里插入图片描述

同时拍500000个数

在这里插入图片描述
排序到这里选择排序就已经非常慢了
我们笔记本是 i9 的 cpu 配置还算可以
跑的时候风扇已经呜呜转了

堆排 1 亿个数

在这里插入图片描述

相关文章:

【数据结构】选择排序——选择排序 和 堆排序

选择排序 和 堆排序 一、选择排序选择排序的思路及其代码选择排序的弊端 二、堆排序三、速度对比同时排10000个数同时排100000个数同时拍500000个数堆排 1 亿个数 一、选择排序 选择排序的思路及其代码 选择排序思路很简单 就是经过将数组遍历选择最小值 将最小值位置的数与数…...

P11229 [CSP-J 2024] 小木棍

[CSP-J 2024] 小木棍 题目描述 小 S 喜欢收集小木棍。在收集了 n n n 根长度相等的小木棍之后&#xff0c;他闲来无事&#xff0c;便用它们拼起了数字。用小木棍拼每种数字的方法如下图所示。 现在小 S 希望拼出一个正整数&#xff0c;满足如下条件&#xff1a; 拼出这个数…...

【学习笔记】SAP ABAP——OPEN SQL(一)【SELECT语句】

SELECT语句简介 SELECT <lines> <columns> FROM <db> WHERE <condition>其中代表查询的件数&#xff0c;代表查询的字段名 SELECT SINGLE SELECT SINGLE <cols> FROM <db> WHERE <condition>该语句用于从数据库表中查询单条数据 …...

SQL注入(1)

1.数字型注入 例如PHP代码 “ Select username from users where id”.&#xff04;&#xff3f;GET&#xff3b;id&#xff3d; 可以注意到&#xff0c;用户的输入ID字段没有任何过滤的&#xff0c;被直接拼接在了SQL查询语句中&#xff0c;由于ID没有被引号包裹&#xff…...

在AI时代,如何解决人的工作岗位被AI替代的问题?

在AI时代&#xff0c;工作岗位被AI替代的问题确实是一个重要的社会课题。随着技术的不断进步&#xff0c;许多传统的工作变得自动化&#xff0c;这带来了效率的提升&#xff0c;但也引发了就业方面的挑战。要应对这一问题&#xff0c;我们可以从以下几方面入手&#xff1a; 促进…...

Linux命令--paste

简介 paste命令用于合并文件行 参数说明 -d: 自定义间隔符&#xff0c;默认为tab -s&#xff1a;串行处理&#xff0c;非并行 示例 将两个文件&#xff0c;按照行合并 demo1.conf内容如下&#xff1a; name domain ip area user password roledemo2.conf内容如下 test t…...

数据结构模拟题[九]

数据结构试卷&#xff08;九&#xff09; 一、选择题 (30 分) 1&#xff0e;下列程序段的时间复杂度为&#xff08; &#xff09;。 for(i0 &#xff1b; i<m &#xff1b; i) for(j0 &#xff1b; j<t &#xff1b; j) c[i][j]0 &#xff1b; for(i0 &#xff1b; i…...

2024年10月国产数据库大事记-墨天轮

本文为墨天轮社区整理的2024年10月国产数据库大事件和重要产品发布消息。 目录 2024年10月国产数据库大事记 TOP102024年10月国产数据库大事记&#xff08;时间线&#xff09;产品/版本发布代表厂商大事记信创数据库上市公司2024年Q3财报 达梦数据&#xff1a;2024年前三季度…...

Andon 业务流程业务开发陷阱----从真实用户与管理者视角逻辑差异

Q : Andon 问题识别归类(就是问题的3层细化)&#xff0c;是在事中&#xff0c;还是在事后? A : 不存在事中就细化归类&#xff0c;有悖于生产问题解决流程。 从操作员的角度来看&#xff0c;他们在事中可能只能识别出存在质量问题&#xff0c;但无法进行具体的质量问题编号…...

Python闭包|你应该知道的常见用例(上)

引言 在 Python 编程语言中&#xff0c;闭包通常指的是一个嵌套函数&#xff0c;即在一个函数内部定义的另一个函数。这个嵌套的函数能够访问并保留其外部函数作用域中的变量。这种结构就构成了一个闭包。 闭包在函数式编程语言中非常普遍。在 Python 中&#xff0c;闭包特别有…...

printf影响单片机中断速度

printf是我们常用的调试程序的手段&#xff0c;在第一版程序中&#xff0c;经常会使用printf来验证程序是否工作正确。这样的调试手段应该在正式版的程序发布前注释掉或者删除。而且不当地使用printf也会带来某些功能性问题&#xff0c;例如&#xff0c;在某项目中&#xff0c;…...

JavaScript 23种经典设计模式简介

23种JavaScript经典设计模式 JavaScript经典设计模式 通过之前的学习&#xff0c;我们知道设计模式是一种解决代码组织、代码复用和代码可维护性等问题的技术方法。它通过将代码以特定的方式组织起来&#xff0c;使代码结构更加清晰、可读性更高、易于维护和扩展。为了在开发…...

位运算相关算法

一、异或运算介绍 1、性质介绍 异或运算&#xff08;XOR&#xff0c;Exclusive OR&#xff09;是一种位运算符。对于两个位进行异或操作&#xff0c;当且仅当这两个位不同时&#xff0c;结果为 1&#xff1b;如果相同&#xff0c;则结果为 0。 A B A^B00001 1 101110 任何数…...

解决:无法在此设备上激活Windows因为无法连接到你的组织的激活服务器

问题&#xff1a; 桌面右下角会出现这个东西&#x1f447; 在设置里查看激活状态就会看到&#x1f447; 解决方法 &#xff1a; 1.打开CMD 搜索CMD&#xff0c;然后以管理员身份运行 2.设置 KMS服务器 1&#xff09;命令行输入&#xff1a; slmgr /skms kms.03k.org 然后…...

【Spring】——SpringBoot项目创建

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 引入 一&#xff1a;介绍 二&#xff1a;Spring Boot项目创建 0&#xff1a;项目目录 1&#xff1a…...

聊一聊:ChatGPT搜索引擎会取代谷歌和百度吗?

当地时间 10 月 31 日&#xff0c;OpenAI 正式推出了 ChatGPT 搜索功能&#xff0c;能实时、快速获取附带相关网页来源链接的答案。这一重大升级标志着其正式向谷歌的搜索引擎霸主地位发起挑战。 本周五我们聊一聊&#xff1a; 欢迎在评论区畅所欲言&#xff0c;分享你的观点~ …...

分布式中常见的问题及其解决办法

分布式中常见的问题及其解决办法 一、多个微服务要操作同一个存储在redis中的变量&#xff0c;如何确保这个变量的正确性 答&#xff1a; 在多个微服务操作同一个存储在Redis中的变量时&#xff0c;可以采取以下措施来确保变量的正确性&#xff1a; 1、使用Redis的事务&…...

HTML 基础标签——多媒体标签<img>、<object> 与 <embed>

文章目录 1. `<img>` 标签主要属性示例注意事项2. `<object>` 标签概述主要属性示例注意事项3. `<embed>` 标签概述主要属性示例注意事项小结在现代网页设计中,多媒体内容的使用变得越来越重要,因为它能够有效增强用户体验、吸引注意力并传达信息。HTML 提…...

word mathml 创建粗体字母快捷键

在 mathml 中达到latex中 \mathbf{A} 的效果 由于word本身不支持这个命令&#xff0c;所以打算用快捷键实现 快捷键的功能是加粗光标前一个字目 1. Alt F8 打开宏&#xff0c;如果打不开可以尝试 Alt Fn F8 2. 输入 BoldPreviousCharacter 新建宏&#xff1a; Sub Bold…...

ROOT添加用户提示权限不够

有个系统已经上线过了&#xff0c;之后测评整改要求不能用root启动中间件&#xff0c;我就想着添加一个普通用户&#xff0c;赋予指定目录权限&#xff0c;然后启动应用就行了 。 结果用root用户创建账号提示权限不够&#xff0c;确认了几遍&#xff0c;是root 命令前面加sud…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Nginx server_name 配置说明

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

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...