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

【数据结构】选择排序

🍬个人主页:Yanni.—

🌈数据结构:Data Structure.​​​​​​

🎂C语言笔记:C Language Notes

🏀OJ题分享: Topic Sharing

目录

前言:

基本思想

直接选择排序

思路分析

 代码实现

堆排序

知识补充

代码思路分析

向下调整算法

建堆算法

堆排序实现

代码实现


前言:

在前面学习了直接插入排序和希尔排序,今天实现选择排序中的直接选择排序和堆排序。堆排序的效率非常高,认真学习之后会学到一个很好的排序方法!

基本思想

每一次从待排序的数据中选出最小(或最大)的一个元素,存放在序列的起始位置,知道全部待排序的数据元素排完。

直接选择排序

思路分析

1.在元素集合array[i]--array[n-1]中选择关键码最大()的数据元素
2.若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
3.在剩余的array[i]--array[n-2]array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素 

 代码实现

这里的代码优化了一下,在正常的普通直接选择排序选择出最小的排在第一位情况下,我这里用了头begin和尾end可以同时把最大值和最小值选出来,然后分别给到相应的位置,这样时间上会比普通的快上一倍。 

void SelectSort(int* a, int n)
{int begin = 0;int end = n-1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);//如果maxi与begin位置重叠,需要矫正if (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);begin++;end--;}
}

堆排序

知识补充

1.堆的逻辑结构是一颗完全二叉树

2.堆的物理结构是一个数组

其中父子节点的关系:(这个很重要!!!

leftchild = parent*2 +1

rightchile = parent*2 +2

parent = (child-1)/2

      

 要用到堆排序,首先要知道两个重要的概念大顶堆和小顶堆。

大顶堆(最大堆):所有的父亲大于等于孩子。

小顶堆(最小堆):所以的父亲小于等于孩子。

代码思路分析

向下调整算法

向下调整算法的前提是左右子树必须是小堆(栈顶的数据是最小的)或着大堆(栈顶数据是最大的)。

 如图,图中左右子树都是小堆,那么就可以使用向下调整。

1.将孩子中最大的选出来。

2.将孩子中最大的与父亲比较大小,如果实现的是建小堆的话,孩子比父亲小,孩子就与父亲交换位置。孩子比父亲大,反之。

void AdjustDown(int* a, int n, int root)
{int parent = root;int child = parent*2 + 1;//默认是左孩子 因为右孩子等于左孩子加一while (child < n){//选择出孩子中最大的一个去与父母比较if (child + 1 < n && a[child] < a[child + 1]){child += 1;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent*2 + 1;}else{break;}}
}

建堆算法

如下图,我们知道了向下调整算法,可如果左右子树不是小堆或大堆呢?我们该怎么实先小顶堆或者大顶堆。

可以发现,如果从8这个最后一个父亲节点开始向下调整,再到7,2,5,3。那么就可以实现了。

总而言之就是建堆的思路就是:从倒数第一个非叶子节点开始调整。

for (int i = (n - 1 - 1)/2; i >= 0; i--)
{AdjustDown(a, n, i);
}

图中n-1表示最后一个节点,根据parent = (child -1)/2可以计算出倒数第一个非叶子节点。

堆排序实现

接下来将数据排成升序,那么建堆是建小堆还是建大堆,这就要我们去分析了。

因为如果是建小堆,那么堆顶的数就是最小的,会被直接选择出去作为第一个数,那么只能第二个数作为根,这样剩下的数关系就全乱了,再重新建堆,时间复杂度就会增加跟多,那就失去了堆排序的意义。所以我们这里建大堆。

建大堆之后,再将最大的数据换到最后,不把他看作堆里面的数据,然后进行向下调整算法就可以选出次小,次小换到倒数第二个位置,再继续调堆,选出第三小....

int end = n - 1;
while (end > 0)
{Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;
}

代码实现

//向下调整
void AdjustDown(int* a, int n, int root)
{int parent = root;int child = parent*2 + 1;//默认是左孩子 因为右孩子等于左孩子加一while (child < n){//选择出孩子中最大的一个去与父母比较if (child + 1 < n && a[child] < a[child + 1]){child += 1;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent*2 + 1;}else{break;}}
}
//堆排序
//升序  建大堆 整体时间复杂度o(N*logN)
void HeapSort(int* a, int n)
{//建堆,时间复杂度为o(N)for (int i = (n - 1 - 1)/2; i >= 0; i--){AdjustDown(a, n, i);}// 排升序,建大堆还是小堆?建大堆int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

好啦,这就是今天学习的分享啦!看到希望大家的三连呀!

如果有不当之处,欢迎大佬指正!

相关文章:

【数据结构】选择排序

&#x1f36c;个人主页&#xff1a;Yanni.— &#x1f308;数据结构&#xff1a;Data Structure.​​​​​​ &#x1f382;C语言笔记&#xff1a;C Language Notes &#x1f3c0;OJ题分享&#xff1a; Topic Sharing 目录 前言&#xff1a; 基本思想 直接选择排序 思路分…...

国产GD32单片机开发入门(二)GD32单片机详解

文章目录 一.概要二.单片机型号命名规则三.GD32F103系统架构四.GD32F103C8T6单片机启动流程五.GD32F103C8T6单片机主要外设资源六.单片机开发过程中查看芯片数据手册的必要性1.单片机外设资源情况2.GD32单片机内部框图3.GD32单片机管脚图4.GD32单片机每个管脚功能5.单片机功耗数…...

8个我平时每天都会看的网站,涵盖办公、娱乐、学习等

分享8个我平时每天都会看的网站&#xff0c;涵盖办公、娱乐、学习等多种类别&#xff0c;试过就知道有多好用&#xff01; 1、MyFreeMP3 tools.liumingye.cn/music/#/ 一个可以免费听歌的平台&#xff0c;不用充会员&#xff0c;里面收录了大多数的国内外知名流行歌手、乐队的…...

Vue2——父子之间间的调用

1、父组件给子组件传值使用props 父组件&#xff1a; <div><SonPage msg"通过props传递值---父>子" ></SonPage><h1>父组件</h1></div> 子组件 <div :style"{border: 1px solid red}"><h1>子组件…...

xfs Vs ext4?

xfs测试 ext4 测试 对比 XFS和EXT4都是Linux系统中广泛使用的文件系统&#xff0c;它们各有特点和优势&#xff0c;选择哪一个取决于你的具体需求和使用场景。下面是它们的主要特点&#xff1a; XFS: 由Silicon Graphics Inc.开发&#xff0c;最初用于SGI的IRIX系统。支持非…...

数据结构stack (笔记)

文章目录 1. 概念理解易混淆内容 2. 时间复杂度3. 实现方式4. 应用5. 内容出处 1. 概念理解 stack(中文名&#xff1a;堆栈、栈)&#xff1a;虽然它叫堆栈&#xff0c;但是它其实指的是栈&#xff0c;跟堆没啥关系。 栈的特性&#xff1a;先进后出、后进先出(这个过程就…...

SQL - 创建 表和数据库

创建和删除数据库 create database if not exists sql_store2; //创建 drop database if exists sql_store2; //删除 -- 创建数据库 create database if not exists sql_store2; drop database if exists sql_store2; 创建表 create table customers (someting); -- 创建表 cre…...

使用 Arch Linux 几个月有感 | 为什么我选择 Arch Linux ,Arch 的优缺点有什么 | 一些Linux发行版推荐

&#xff08;终端是 Yakuake &#xff0c;KDE 自带&#xff09; 一点碎碎念&#xff0c;可以跳过不看 几年前从 CentOS 接触的 Linux &#xff0c;试图搭建一个KMS服务器 但是失败了 &#xff0c;后来装过 Ubuntu Debian deepin Kali Kubuntu Manjaro&#xff0c;踩一路坑最后…...

SQLserver中的增删改查和数据类型

SQLserver增删查改语句 SQL Server 是一种关系数据库管理系统&#xff0c;用于存储、管理和检索数据。以下是一些基本的 SQL 语句&#xff0c;用于在 SQL Server 中执行增删查改操作&#xff1a; 插入数据&#xff08;Insert&#xff09; 插入完整行&#xff1a; INSERT INTO …...

个人收藏个性化、实用性、可玩性在线网站持续更新,与君共享

1.https://handraw.top/ 支持中文手绘效果的白板工具&#xff0c;比较怀旧复古风格 界面简单风 2.https://app.diagrams.net 流程图、UML图、网络图、组织结构图、思维导图等&#xff0c;比较专业 可导出图片 PDF HTLM等各种格式 3.https://www.processon.com 主要用于生成…...

win10蓝牙只能发送,无法接收

给win10升了级&#xff0c;到22H2&#xff0c;蓝牙出了问题 以前接收&#xff0c;就是默认直接就可以接收。现在只能发送&#xff0c;无法接收。 在网上找了很多办法都没奏效&#xff0c;目前的方法是&#xff0c; 每次接收&#xff0c;都要操作一次&#xff0c;而不是自动接…...

【论文阅读03】用于海洋物体检测的多注意力路径聚合网络

来源&#xff1a;用于海洋物体检测的多注意力路径聚合网络 |应用智能 (springer.com) 一、背景&#xff1a; 水下图像存在偏色、对比度低、能见度低等问题&#xff0c;使得海洋物体难以被探测到。这些都增加了海上目标探测的难度。 目前流行的检测器方法是基于卷积神经网络&…...

Linux 进程(2)

进程的回收 1.wait 原型 pid_t wait(int *status); 功能&#xff1a;该函数可以阻塞等待任意子进程退出 并回收该进程的状态。 一般用于父进程回收子进程状态。 参数&#xff1a;status 进程退出时候的状态 如果不关心其退出状态一般用NULL表示 如果要回收进程…...

[CSCCTF 2019 Qual]FlaskLight1

打开题目 右键查看一下源代码 看到提示&#xff0c;需要用GET方search函数...

layui table表单 checkbox选中一个其它也要选中

当我们选中其中一个商品的时候同类型的商品状态也要跟着改变 所以要在表单加载完成后去监听checkbox ,done:function (res) {console.log(详情表格数据,res)tableDetailList res.data;// 监听表格复选框选择table.on(checkbox( INST_SELECTORS.instLayFilters.unpaidTableDe…...

【pip镜像设置】pip使用清华镜像源安装

文章目录 问题&#xff1a;问题描述原因分析&#xff1a;PyPI&#xff08;Python Package Index&#xff09; PypI 镜像列表解决方案&#xff1a; 问题&#xff1a; 大家经常会使用 pip 进行python 的第三方库安装&#xff0c;但是&#xff0c;有时会出现 ERROR: Could not f…...

c++ 智能指针--std::shared_ptr

在C中&#xff0c;std::shared_ptr是智能指针的一种&#xff0c;它用于自动管理具有动态生命周期的对象。当std::shared_ptr的实例被销毁或重置时&#xff0c;它所指向的对象&#xff08;如果仍然存在&#xff09;将被自动删除&#xff08;调用delete&#xff09;&#xff0c;前…...

网络工程师学习笔记(二)

计算机网络概述——二 通信子网中转发节点的互联模式叫做子网的拓扑结构 常见的拓扑结构&#xff1a; 总线型(一条总干线上连接着多个终端) 特点&#xff1a;损坏一个节点会造成单点故障 星型&#xff08;中间一台服务器或者一各小型工作站周围都是计算机&#xff09; 特点…...

90.WEB渗透测试-信息收集-Google语法(4)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;89.WEB渗透测试-信息收集-Google语法&#xff08;3&#xff09; • inurl • 搜索特殊 UR…...

阿里Qwen2开源大模型本地部署及调试全攻略

阿里Qwen2开源大模型本地部署及调试全攻略 #Qwen2系列大模型性能卓越&#xff0c;超越业界知名模型。开源后受到AI开发者关注&#xff0c;支持多种语言&#xff0c;提升多语言理解。在预训练和微调上优化&#xff0c;实现智能水平提升。Qwen2系列模型在各项能力上均领先&#…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

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可以提供外设…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...