当前位置: 首页 > 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系列模型在各项能力上均领先&#…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

相关类相关的可视化图像总结

目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系&#xff0c;可直观判断线性相关、非线性相关或无相关关系&#xff0c;点的分布密…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...

CTF show 数学不及格

拿到题目先查一下壳&#xff0c;看一下信息 发现是一个ELF文件&#xff0c;64位的 ​ 用IDA Pro 64 打开这个文件 ​ 然后点击F5进行伪代码转换 可以看到有五个if判断&#xff0c;第一个argc ! 5这个判断并没有起太大作用&#xff0c;主要是下面四个if判断 ​ 根据题目…...