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

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...