【数据结构详解】——选择排序(动图详解)
目录
- 🕒 1. 直接选择排序
- 🕒 2. 堆排序
🕒 1. 直接选择排序
💡 算法思想:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始(末尾)位置,然后选出次小(或次大)的一个元素,存放在最大(最小)元素的下一个位置,重复这样的步骤直到全部待排序的数据元素排完。

代码实现如下:这里可以进行一个优化,最小值和最大值同时选,然后将最小值与起始位置交换,将最大值与末尾位置交换。
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n)
{int begin = 0; // 起始位置int end = n - 1; // 结束位置// 循环直到整个数组都被排序while (begin < end){int mini = begin; // 保存最小元素下标int maxi = begin; // 保存最大元素下标// 在当前未排序部分查找最小和最大元素的下标for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i; // 更新最小元素下标}if (a[i] > a[maxi]){maxi = i; // 更新最大元素下标}}// 将找到的最小元素交换到起始位置Swap(&a[begin], &a[mini]);// 如果最大元素的位置在起始位置,更新最大元素下标为 miniif (maxi == begin){maxi = mini;}// 将找到的最大元素交换到末尾位置Swap(&a[end], &a[maxi]);// 缩小排序范围++begin;--end;}
}

选择排序的特性总结:
- 选择排序步骤非常好理解,但是效率不是很好(不论数组是否有序都会执行原步骤),实际中很少使用。
- 时间复杂度:O(N2)
- 空间复杂度:O(1)
- 稳定性:不稳定
🕒 2. 堆排序
💡 算法思想:堆排序即利用堆的思想来进行排序,总共分为两个步骤:1. 建堆(升序:建大堆;降序:建小堆) 2. 利用堆删除思想来进行排序:建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。
这里以升序为例:
- 首先应该建一个大堆,不能直接使用堆来实现。可以将需要排序的数组看作是一个堆,但需要将数组结构变成堆结构。
- 我们可以从堆从下往上的第二行最右边开始依次向下调整直到调整到堆顶,这样就可以将数组调整成一个堆,且如果建立的是大堆,堆顶元素为最大值。
- 然后按照堆删的思想将堆顶和堆底的数据交换,但不同的是这里不删除最后一个元素。
- 这样最大元素就在最后一个位置,然后从堆顶向下调整到倒数第二个元素,这样次大的元素就在堆顶,重复上述步骤直到只剩堆顶时停止。

// AdjustDown函数:在数组a中,从节点root开始向下调整,使得以root为根的子树满足大顶堆的性质。
void AdjustDown(int* a, int n, int root)
{assert(a);int parent = root; // 当前子树的根节点int child = parent * 2 + 1; // 左孩子节点// 循环直到没有孩子节点while (child < n){// 如果右孩子存在且比左孩子大,则选择右孩子作为比较对象if (child + 1 < n && a[child + 1] > a[child]){child++;}// 如果孩子节点比父节点大,则交换父节点和孩子节点的值,并更新父节点和孩子节点继续向下比较if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break; // 如果孩子节点不再比父节点大,则退出循环}}
}void HeapSort(int* a, int n)
{assert(a);// 建立大顶堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i); // 对每个非叶子节点进行向下调整,建立大顶堆}// 交换堆顶元素和末尾元素,并重新调整堆for (int i = n - 1; i > 0; i--){Swap(&a[i], &a[0]); // 将当前堆顶(最大值)与数组末尾元素交换AdjustDown(a, i, 0); // 调整剩余堆为大顶堆,范围缩小为0到i-1}
}

堆排序的特性总结:
- 堆排序使用堆来选数,效率较高,适用于需要频繁插入和删除的场景。
- 时间复杂度:O(N*logN)
- 空间复杂度:O(1)
- 稳定性:不稳定
❗ 转载请注明出处
作者:HinsCoder
博客链接:🔎 作者博客主页
相关文章:
【数据结构详解】——选择排序(动图详解)
目录 🕒 1. 直接选择排序🕒 2. 堆排序 🕒 1. 直接选择排序 💡 算法思想:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始(末尾)位置…...
杂项命令(笔记)
ifconfig :http://t.csdnimg.cn/gT2AR echo :http://t.csdnimg.cn/6DSoO ps和top的区别 http://t.csdnimg.cn/f1XWt...
代码随想录算法训练营Day38||完全背包问题、leetcode 518. 零钱兑换 II 、 377. 组合总和 Ⅳ 、70. 爬楼梯 (进阶)
一、完全背包问题 相较于01背包,完全背包的显著特征是每个物品可以用无数次,遍历顺序也不需要为了保证每个物品只去一次而倒序遍历。 #include<iostream> #include<vector> using namespace std; int main(){int N,V;cin>>N>>V…...
超越链端:Web3的无边界技术革命
Web3,作为互联网技术的第三代变革,正以其去中心化、开放透明的特性,重新定义着我们的数字生活。在这一背景下,“链端”概念逐渐成为热点,意味着我们不仅仅局限于区块链技术本身,而是探索其在更广泛领域的应…...
127. Go反射基本原理
文章目录 反射基础 - go 的 interface 是怎么存储的?iface 和 eface 的结构体定义(runtime/iface.go):_type 是什么?itab 是什么? 反射对象 - reflect.Type 和 reflect.Value反射三大定律Elem 方法reflect.…...
提高PDF电子书的分辨率
解决方法出处 1. 安装ImageMagick brew install imagemagick brew install ghostscript2. 按流程进行 convert -density 600 your_pdf_filename.pdf output-%02d.jpg convert output*.jpg -normalize -threshold 80% final-%02d.jpg convert final*.jpg my_new_highcontras…...
Spring Cloud全解析:注册中心之zookeeper注册中心
zookeeper注册中心 使用zookeeper作为注册中心就不需要像eureka一样,在写一个eureka-server的服务了,因为zookeeper本身就是一个服务端,只需要编写需要进行服务注册的客户端即可 依赖 <!-- zookeeper 注册中心 --> <dependency&g…...
解决戴尔台式电脑休眠后无法唤醒问题
近期发现有少量戴尔的台式机会有休眠后无法唤醒的问题,具体现象就是电脑在休眠后,电源指示灯以呼吸的频率闪烁,无论怎么点鼠标和键盘都没有反应,并且按开机按钮也没法唤醒,只能是长按开机键强制关机再重启才行…...
MySQL运维-分库分表
介绍 问题分析 拆分策略 垂直拆分 水平拆分 实现技术 Mycat概述 介绍 概念介绍 Mycat配置 schema.xml schema标签 schema标签(table) datanode标签 datahost标签 rule.xml sever.xml system标签 user标签 Mycat分片 分片规则-范围 分片规则-取模 分…...
AGX orin硬件设计
AGX orin简介 从硬件组成来说,AGX orin可以分为核心板和扩展板。 核心板 核心板就是英伟达原装板卡,如下图所示: 核心板分为32G内存版本和64内存版本,两个版本除去内存不同之外,CPU也略有差异。核心板通过…...
AI大模型开发——2.深度学习基础(1)
学习大模型开发之前,我们需要有足够的储备知识,类似于基础的python语法相信大家也都是十分熟悉了。所以笔者也是考虑了几天决定先给大家补充一些深度学习知识。 首先问大家一个问题,学习大模型之前为什么要先学习深度学习知识呢? …...
go语言day22 gin-vue-admin全栈项目的依赖安装
flipped-aurora/gin-vue-admin: 🚀ViteVue3Gin的开发基础平台,支持TS和JS混用。它集成了JWT鉴权、权限管理、动态路由、显隐可控组件、分页封装、多点登录拦截、资源权限、上传下载、代码生成器【可AI辅助】、表单生成器和可配置的导入导出等开发必备功能…...
PHP之docker学习笔记
Docker学习笔记 前言: 之前学过一遍忘了 那就再来一遍没啥好说的就是可以直接构建一个环境 然后方便部署官网 http://www.docker.com仓库 https://hub.docker.comDocker的基本组成 镜像 容器 仓库 安装与卸载 卸载 sudo yum remove docker \docker-client \dock…...
基于树莓派4B与STM32的UART串口通信实验(代码开源)
在现代嵌入式系统中,树莓派和STM32的结合使用已成为一种流行趋势,它们各自承担不同的角色,实现优势互补。树莓派以其强大的计算能力处理复杂算法,而STM32则以其高效的控制能力执行实际的硬件操作。本文将详细介绍如何实现基于树莓…...
【云服务器系列】基于华为云OBS实现Picgo和Typora的完美融合
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
IIC协议
一、IIC协议 1.1 IIC协议概述 IIC全称Inter-Integrated Circuit (集成电路总线) 是由PHILIPS(飞利浦)公司在80年代开发的两线式串行总线,用于连接微控制器及其外围设备。IIC属于半双工同步通信方式 特点 简单性和有效性。 由于接口直接在组件之上,…...
如何在linux系统上部署nginx
1)首先去 nginx.org/download 官网下载你所需要的版本 我这里是下载的 nginx-1-23-3.tar.gz 2)然后执行 yum -y install lrzsz 安装文件上传软件 执行 rz 选择你下载nginx的位置进行上传 yum -y install lrzsz 3)执行 tar -zxvf nginx-1.23…...
香港网站服务器抵御恶意攻击的一些措施
香港网站服务器因为在互联网中扮演着重要的角色,因此也在面临着网络中各种恶意攻击的威胁,为了确保香港网站服务器的安全和稳定运行,可以通过安全措施来进行防御,本文就来分享一些香港网站服务器来抵御恶意攻击的关键措施。 一、网…...
实战:docker部署filesite.io完美解决家庭相册需求-2024.8.10(测试成功)
https://wiki.onedayxyy.cn/docs/filesite.io-photot-install-full...
美团到店面经
redis中大key引起的问题 1、阻塞请求 Big Key对应的value较大,我们对其进行读写的时候,需要耗费较长的时间,这样就可能阻塞后续的请求处理。Redis的核心线程是单线程,单线程中请求任务的处理是串行的,前面的任务完不成…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
