【数据结构】选择排序

🍬个人主页:Yanni.—
🌈数据结构:Data Structure.
🎂C语言笔记:C Language Notes
🏀OJ题分享: Topic Sharing
目录
前言:
基本思想
直接选择排序
思路分析
代码实现
堆排序
知识补充
代码思路分析
向下调整算法
建堆算法
堆排序实现
代码实现
前言:
在前面学习了直接插入排序和希尔排序,今天实现选择排序中的直接选择排序和堆排序。堆排序的效率非常高,认真学习之后会学到一个很好的排序方法!
基本思想
每一次从待排序的数据中选出最小(或最大)的一个元素,存放在序列的起始位置,知道全部待排序的数据元素排完。
直接选择排序
思路分析

代码实现
这里的代码优化了一下,在正常的普通直接选择排序选择出最小的排在第一位情况下,我这里用了头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--;}
}
好啦,这就是今天学习的分享啦!看到希望大家的三连呀!
如果有不当之处,欢迎大佬指正!
相关文章:
【数据结构】选择排序
🍬个人主页:Yanni.— 🌈数据结构:Data Structure. 🎂C语言笔记:C Language Notes 🏀OJ题分享: Topic Sharing 目录 前言: 基本思想 直接选择排序 思路分…...
国产GD32单片机开发入门(二)GD32单片机详解
文章目录 一.概要二.单片机型号命名规则三.GD32F103系统架构四.GD32F103C8T6单片机启动流程五.GD32F103C8T6单片机主要外设资源六.单片机开发过程中查看芯片数据手册的必要性1.单片机外设资源情况2.GD32单片机内部框图3.GD32单片机管脚图4.GD32单片机每个管脚功能5.单片机功耗数…...
8个我平时每天都会看的网站,涵盖办公、娱乐、学习等
分享8个我平时每天都会看的网站,涵盖办公、娱乐、学习等多种类别,试过就知道有多好用! 1、MyFreeMP3 tools.liumingye.cn/music/#/ 一个可以免费听歌的平台,不用充会员,里面收录了大多数的国内外知名流行歌手、乐队的…...
Vue2——父子之间间的调用
1、父组件给子组件传值使用props 父组件: <div><SonPage msg"通过props传递值---父>子" ></SonPage><h1>父组件</h1></div> 子组件 <div :style"{border: 1px solid red}"><h1>子组件…...
xfs Vs ext4?
xfs测试 ext4 测试 对比 XFS和EXT4都是Linux系统中广泛使用的文件系统,它们各有特点和优势,选择哪一个取决于你的具体需求和使用场景。下面是它们的主要特点: XFS: 由Silicon Graphics Inc.开发,最初用于SGI的IRIX系统。支持非…...
数据结构stack (笔记)
文章目录 1. 概念理解易混淆内容 2. 时间复杂度3. 实现方式4. 应用5. 内容出处 1. 概念理解 stack(中文名:堆栈、栈):虽然它叫堆栈,但是它其实指的是栈,跟堆没啥关系。 栈的特性:先进后出、后进先出(这个过程就…...
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发行版推荐
(终端是 Yakuake ,KDE 自带) 一点碎碎念,可以跳过不看 几年前从 CentOS 接触的 Linux ,试图搭建一个KMS服务器 但是失败了 ,后来装过 Ubuntu Debian deepin Kali Kubuntu Manjaro,踩一路坑最后…...
SQLserver中的增删改查和数据类型
SQLserver增删查改语句 SQL Server 是一种关系数据库管理系统,用于存储、管理和检索数据。以下是一些基本的 SQL 语句,用于在 SQL Server 中执行增删查改操作: 插入数据(Insert) 插入完整行: INSERT INTO …...
个人收藏个性化、实用性、可玩性在线网站持续更新,与君共享
1.https://handraw.top/ 支持中文手绘效果的白板工具,比较怀旧复古风格 界面简单风 2.https://app.diagrams.net 流程图、UML图、网络图、组织结构图、思维导图等,比较专业 可导出图片 PDF HTLM等各种格式 3.https://www.processon.com 主要用于生成…...
win10蓝牙只能发送,无法接收
给win10升了级,到22H2,蓝牙出了问题 以前接收,就是默认直接就可以接收。现在只能发送,无法接收。 在网上找了很多办法都没奏效,目前的方法是, 每次接收,都要操作一次,而不是自动接…...
【论文阅读03】用于海洋物体检测的多注意力路径聚合网络
来源:用于海洋物体检测的多注意力路径聚合网络 |应用智能 (springer.com) 一、背景: 水下图像存在偏色、对比度低、能见度低等问题,使得海洋物体难以被探测到。这些都增加了海上目标探测的难度。 目前流行的检测器方法是基于卷积神经网络&…...
Linux 进程(2)
进程的回收 1.wait 原型 pid_t wait(int *status); 功能:该函数可以阻塞等待任意子进程退出 并回收该进程的状态。 一般用于父进程回收子进程状态。 参数:status 进程退出时候的状态 如果不关心其退出状态一般用NULL表示 如果要回收进程…...
[CSCCTF 2019 Qual]FlaskLight1
打开题目 右键查看一下源代码 看到提示,需要用GET方search函数...
layui table表单 checkbox选中一个其它也要选中
当我们选中其中一个商品的时候同类型的商品状态也要跟着改变 所以要在表单加载完成后去监听checkbox ,done:function (res) {console.log(详情表格数据,res)tableDetailList res.data;// 监听表格复选框选择table.on(checkbox( INST_SELECTORS.instLayFilters.unpaidTableDe…...
【pip镜像设置】pip使用清华镜像源安装
文章目录 问题:问题描述原因分析:PyPI(Python Package Index) PypI 镜像列表解决方案: 问题: 大家经常会使用 pip 进行python 的第三方库安装,但是,有时会出现 ERROR: Could not f…...
c++ 智能指针--std::shared_ptr
在C中,std::shared_ptr是智能指针的一种,它用于自动管理具有动态生命周期的对象。当std::shared_ptr的实例被销毁或重置时,它所指向的对象(如果仍然存在)将被自动删除(调用delete),前…...
网络工程师学习笔记(二)
计算机网络概述——二 通信子网中转发节点的互联模式叫做子网的拓扑结构 常见的拓扑结构: 总线型(一条总干线上连接着多个终端) 特点:损坏一个节点会造成单点故障 星型(中间一台服务器或者一各小型工作站周围都是计算机) 特点…...
90.WEB渗透测试-信息收集-Google语法(4)
免责声明:内容仅供学习参考,请合法利用知识,禁止进行违法犯罪活动! 内容参考于: 易锦网校会员专享课 上一个内容:89.WEB渗透测试-信息收集-Google语法(3) • inurl • 搜索特殊 UR…...
阿里Qwen2开源大模型本地部署及调试全攻略
阿里Qwen2开源大模型本地部署及调试全攻略 #Qwen2系列大模型性能卓越,超越业界知名模型。开源后受到AI开发者关注,支持多种语言,提升多语言理解。在预训练和微调上优化,实现智能水平提升。Qwen2系列模型在各项能力上均领先&#…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...
