【数据结构】选择排序

🍬个人主页: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系列模型在各项能力上均领先&#…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
【若依】框架项目部署笔记
参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作: 压缩包下载:http://download.redis.io/releases 1. 上传压缩包,并进入压缩包所在目录,解压到目标…...
【threejs】每天一个小案例讲解:创建基本的3D场景
代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone,无需安装依赖,直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景(Scene) 使用 THREE.Scene(…...
