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

【数据结构详解】——选择排序(动图详解)

目录

  • 🕒 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;}
}

在这里插入图片描述

选择排序的特性总结:

  1. 选择排序步骤非常好理解,但是效率不是很好(不论数组是否有序都会执行原步骤),实际中很少使用。
  2. 时间复杂度:O(N2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

🕒 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}
}

在这里插入图片描述

堆排序的特性总结:

  1. 堆排序使用堆来选数,效率较高,适用于需要频繁插入和删除的场景。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

❗ 转载请注明出处
作者:HinsCoder
博客链接:🔎 作者博客主页

相关文章:

【数据结构详解】——选择排序(动图详解)

目录 &#x1f552; 1. 直接选择排序&#x1f552; 2. 堆排序 &#x1f552; 1. 直接选择排序 &#x1f4a1; 算法思想&#xff1a;第一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c;存放在序列的起始&#xff08;末尾&#xff09;位置…...

杂项命令(笔记)

ifconfig &#xff1a;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背包&#xff0c;完全背包的显著特征是每个物品可以用无数次&#xff0c;遍历顺序也不需要为了保证每个物品只去一次而倒序遍历。 #include<iostream> #include<vector> using namespace std; int main(){int N,V;cin>>N>>V…...

超越链端:Web3的无边界技术革命

Web3&#xff0c;作为互联网技术的第三代变革&#xff0c;正以其去中心化、开放透明的特性&#xff0c;重新定义着我们的数字生活。在这一背景下&#xff0c;“链端”概念逐渐成为热点&#xff0c;意味着我们不仅仅局限于区块链技术本身&#xff0c;而是探索其在更广泛领域的应…...

127. Go反射基本原理

文章目录 反射基础 - go 的 interface 是怎么存储的&#xff1f;iface 和 eface 的结构体定义&#xff08;runtime/iface.go&#xff09;&#xff1a;_type 是什么&#xff1f;itab 是什么&#xff1f; 反射对象 - 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一样&#xff0c;在写一个eureka-server的服务了&#xff0c;因为zookeeper本身就是一个服务端&#xff0c;只需要编写需要进行服务注册的客户端即可 依赖 <!-- zookeeper 注册中心 --> <dependency&g…...

解决戴尔台式电脑休眠后无法唤醒问题

近期发现有少量戴尔的台式机会有休眠后无法唤醒的问题&#xff0c;具体现象就是电脑在休眠后&#xff0c;电源指示灯以呼吸的频率闪烁&#xff0c;无论怎么点鼠标和键盘都没有反应&#xff0c;并且按开机按钮也没法唤醒&#xff0c;只能是长按开机键强制关机再重启才行&#xf…...

MySQL运维-分库分表

介绍 问题分析 拆分策略 垂直拆分 水平拆分 实现技术 Mycat概述 介绍 概念介绍 Mycat配置 schema.xml schema标签 schema标签&#xff08;table&#xff09; datanode标签 datahost标签 rule.xml sever.xml system标签 user标签 Mycat分片 分片规则-范围 分片规则-取模 分…...

AGX orin硬件设计

AGX orin简介 ​ 从硬件组成来说&#xff0c;AGX orin可以分为核心板和扩展板。 核心板 ​ 核心板就是英伟达原装板卡&#xff0c;如下图所示&#xff1a; ​ 核心板分为32G内存版本和64内存版本&#xff0c;两个版本除去内存不同之外&#xff0c;CPU也略有差异。核心板通过…...

AI大模型开发——2.深度学习基础(1)

学习大模型开发之前&#xff0c;我们需要有足够的储备知识&#xff0c;类似于基础的python语法相信大家也都是十分熟悉了。所以笔者也是考虑了几天决定先给大家补充一些深度学习知识。 首先问大家一个问题&#xff0c;学习大模型之前为什么要先学习深度学习知识呢&#xff1f; …...

go语言day22 gin-vue-admin全栈项目的依赖安装

flipped-aurora/gin-vue-admin: &#x1f680;ViteVue3Gin的开发基础平台&#xff0c;支持TS和JS混用。它集成了JWT鉴权、权限管理、动态路由、显隐可控组件、分页封装、多点登录拦截、资源权限、上传下载、代码生成器【可AI辅助】、表单生成器和可配置的导入导出等开发必备功能…...

PHP之docker学习笔记

Docker学习笔记 前言&#xff1a; 之前学过一遍忘了 那就再来一遍没啥好说的就是可以直接构建一个环境 然后方便部署官网 http://www.docker.com仓库 https://hub.docker.comDocker的基本组成 镜像 容器 仓库 安装与卸载 卸载 sudo yum remove docker \docker-client \dock…...

基于树莓派4B与STM32的UART串口通信实验(代码开源)

在现代嵌入式系统中&#xff0c;树莓派和STM32的结合使用已成为一种流行趋势&#xff0c;它们各自承担不同的角色&#xff0c;实现优势互补。树莓派以其强大的计算能力处理复杂算法&#xff0c;而STM32则以其高效的控制能力执行实际的硬件操作。本文将详细介绍如何实现基于树莓…...

【云服务器系列】基于华为云OBS实现Picgo和Typora的完美融合

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

IIC协议

一、IIC协议 1.1 IIC协议概述 IIC全称Inter-Integrated Circuit (集成电路总线) 是由PHILIPS(飞利浦)公司在80年代开发的两线式串行总线&#xff0c;用于连接微控制器及其外围设备。IIC属于半双工同步通信方式 特点 简单性和有效性。 由于接口直接在组件之上&#xff0c;…...

如何在linux系统上部署nginx

1&#xff09;首先去 nginx.org/download 官网下载你所需要的版本 我这里是下载的 nginx-1-23-3.tar.gz 2&#xff09;然后执行 yum -y install lrzsz 安装文件上传软件 执行 rz 选择你下载nginx的位置进行上传 yum -y install lrzsz 3&#xff09;执行 tar -zxvf nginx-1.23…...

香港网站服务器抵御恶意攻击的一些措施

香港网站服务器因为在互联网中扮演着重要的角色&#xff0c;因此也在面临着网络中各种恶意攻击的威胁&#xff0c;为了确保香港网站服务器的安全和稳定运行&#xff0c;可以通过安全措施来进行防御&#xff0c;本文就来分享一些香港网站服务器来抵御恶意攻击的关键措施。 一、网…...

实战:docker部署filesite.io完美解决家庭相册需求-2024.8.10(测试成功)

https://wiki.onedayxyy.cn/docs/filesite.io-photot-install-full...

美团到店面经

redis中大key引起的问题 1、阻塞请求 Big Key对应的value较大&#xff0c;我们对其进行读写的时候&#xff0c;需要耗费较长的时间&#xff0c;这样就可能阻塞后续的请求处理。Redis的核心线程是单线程&#xff0c;单线程中请求任务的处理是串行的&#xff0c;前面的任务完不成…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

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

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

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...