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

【排序算法】堆排序详解与实现

一、堆排序的思想

         堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆(若不清楚什么是堆,可以看我前面的文章,有详细阐述)来进行选择数据,通过向下调整算法,从第一个非叶子结点开始在局部先创建出大堆(或小堆),然后父亲结点不断往上走,直到整棵树都建成一个堆 需要注意的是排升序要建大堆,排降序建小堆。( 然后不断交换根节点和最后一个节点的值,交换完后节点的数目减1(因为最后一个节点已经是它应该在的位置了,不用再参与建堆),再从根节点向下建堆(除最后一个节点其它节点又会建成一个堆) 然后重复红色括号中的过程,堆排序就完成了。

二、堆排序的图解

下图以建大堆为例排一个升序序列

三、堆排序的实现

3.1向下调整算法的实现

实现堆排序最重要的就是实现向下调整算法。以下是向下调整算法的代码以及解释

//这里以建大堆为例
void AdjustDown(int* a, int n, int root)
{int child = root * 2 + 1;//找到根节点的左孩子while (child < n)//判断左孩子是否出界{if (child + 1 < n && a[child + 1] > a[child])//child + 1 < n判断右孩子是否出界,//a[child + 1] > a[child]判断左右孩子的大小,取左右孩子中大的那一个child++;if (a[child] > a[root])//入过孩子的值比父亲的值大,就交换孩子和父亲的位置Swap(&a[child], &a[root]);else//如果孩子的值不比父亲的值大,就证明大堆已经建好了(因为此时父亲的左右子树都是大堆),//直接break跳出循环。break;//没有break来到这里就顺着子树继续往下走root = child;child = root * 2 + 1;}
}

3.2堆排序的实现

以下是堆排序的代码实现以及解释

void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){//(n - 1 - 1) / 2找到第一个非叶子节点,从第一个非叶子结点开始向下建堆AdjustDown(a, n, i);}//堆建好了int end = n - 1;while (end > 0){//假设是建大堆,将下标为0的元素和下标为end的元素交换,//最大的数就排到最后了,也就相当于最后的那个数已经排好了,不用再参与下面的向下建堆Swap(&a[0], &a[end]);AdjustDown(a, end, 0);//还没有排好的数向下建堆从0位置开始向下建堆end--;}
}

四、总结

堆排序的时间复杂度为 O(N*logN) (向下建堆时间复杂度为O(N),排序时间复杂度为O(N*logN)), 空间复杂度:O(1) ,稳定性:不稳定。

相关文章:

【排序算法】堆排序详解与实现

一、堆排序的思想 堆排序(Heapsort)是指利用堆积树&#xff08;堆&#xff09;这种数据结构所设计的一种排序算法&#xff0c;它是选择排序的一种。它是通过堆&#xff08;若不清楚什么是堆&#xff0c;可以看我前面的文章&#xff0c;有详细阐述&#xff09;来进行选择数据&am…...

java Spring Boot整合jwt实现token生成

先在 pom.xml 文件中注入依赖 <!-- JWT --> <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt-api</artifactId><version>0.11.2</version> </dependency> <dependency><groupId>io.jsonw…...

如何使用Git和GitHub进行版本控制

如何使用Git和GitHub进行版本控制 版本控制是软件开发过程中的重要组成部分&#xff0c;它允许开发者跟踪和管理代码的变化&#xff0c;以确保团队协作顺畅&#xff0c;并帮助在需要时回溯到以前的代码状态。Git和GitHub是最流行的版本控制工具之一&#xff0c;本文将介绍如何…...

彻底解决 WordPress cURL error 28 错误

cURL 连接超时。 这种情况最普遍&#xff0c;这里的超时并不是完全不可连接&#xff0c;而是因为网络状况或其它原因数据传输缓慢&#xff0c;超过连接的时间限制导致传输中断引起的错误。 不论是何种原因导致连接超时&#xff0c;都可以通过增加超时限制来解决此问题。但 UR…...

LLM项目代码改写

背景&#xff1a; 最近在做代码大语言模型生成项目代码的课题。代码生成现在大部分的工作是在做即时代码生成&#xff0c;这个有点类似代码智能提示&#xff0c;只不过生成的可能是一段片段代码&#xff1b;然而对于整个项目代码的生成做的团队并不多&#xff0c;原因大致如下…...

小谈设计模式(14)—建造者模式

小谈设计模式&#xff08;14&#xff09;—建造者模式 专栏介绍专栏地址专栏介绍 建造者模式角色分类产品&#xff08;Product&#xff09;抽象建造者&#xff08;Builder&#xff09;具体建造者&#xff08;Concrete Builder&#xff09;指挥者&#xff08;Director&#xff0…...

【kubernetes】k8s中的选主机制

leader-election选主机制 1 为什么需要leader-election&#xff1f; 在集群中存在某种业务场景&#xff0c;一批相同功能的进程同时运行&#xff0c;但是同一时刻&#xff0c;只能有一个工作&#xff0c;只有当正在工作的进程异常时&#xff0c;才会由另一个进程进行接管。这…...

学生选课系统基础版

第四章java中的集合框架 4.1&#xff1a;java中的集合框架概述 1.java概念与作用 现实中很多事物凑在一起都是集合 如购物车是商品的集合 军队呢 是军人的集合 学校是学生的结合 数学中的集合&#xff1a; 具有共同属性的事物的总体 java中的集合类呢 跟数学的集…...

redis no-appendfsync-on-rewrite

no-appendfsync-on-rewriteyes 当用户请求写入redis的时候&#xff0c;这部分数据只是保存在内存中&#xff0c;主线程并不会马上对此数据进行 aof刷盘&#xff08;而是根据aof刷盘的频率由子线程进行同步&#xff09;&#xff0c;这样子不会阻塞但是会导致数据丢失no-appendfs…...

Spring Cloud Gateway2之路由详解

Spring Cloud Gateway路由 文章目录 1. 前言2. Gateway路由的基本概念3. 三种路由1. 静态路由2. 动态路由1. 利用外部存储2. API动态路由 3. 服务发现路由(自动路由)3.1. 配置方式3.2 自动路由&#xff08;服务发现&#xff09;原理核心源码GatewayDiscoveryClientAutoConfigur…...

阿里云RDS关系型数据库详细介绍_多版本数据库说明

阿里云RDS关系型数据库大全&#xff0c;关系型数据库包括MySQL版、PolarDB、PostgreSQL、SQL Server和MariaDB等&#xff0c;NoSQL数据库如Redis、Tair、Lindorm和MongoDB&#xff0c;阿里云百科分享阿里云RDS关系型数据库大全&#xff1a; 目录 阿里云RDS关系型数据库大全 …...

Vue中的数据绑定

一、v-bind单向数据绑定 单向数据绑定中&#xff0c;数据只能由data流向页面。 v-bind:属性名"data变量" 或简写为 :属性名"data变量" 我们修改data中的iptvalue值&#xff0c;页面input框中的value值改变。 而我们修改input框中的value值&#xff0…...

前后端分离计算机毕设项目之基于SpringBoot的旅游网站的设计与实现《内含源码+文档+部署教程》

博主介绍&#xff1a;✌全网粉丝10W,前互联网大厂软件研发、集结硕博英豪成立工作室。专注于计算机相关专业毕业设计项目实战6年之久&#xff0c;选择我们就是选择放心、选择安心毕业✌ &#x1f345;由于篇幅限制&#xff0c;想要获取完整文章或者源码&#xff0c;或者代做&am…...

[JAVAee]Spring拦截器

适用场景 像是页面的登录验证处理,权限校验,登录日志的处理. 实现步骤 创建⾃定义拦截器,实现 HandlerInterceptor 接⼝的 preHandle&#xff08;执⾏具体⽅法之前的预处理⽅法.将⾃定义拦截器加⼊ WebMvcConfigurer 的 addInterceptors ⽅法中. 下面以登录验证为例,实现拦…...

【nvm】Node Version Manager(NVM)安装配置以及使用(WIN版)

NVM 包管理工具 安装 访问NVM-Windows的GitHub页面&#xff1a;点击nvm-setup.exe。 根据提示进行下一步&#xff0c;文件位置选择自定义位置 验证安装是否成功 nvm version 。如果成功&#xff0c;它将显示NVM的版本号。 使用 nvm list available查看所有的可以被下载…...

【微服务】七. http客户端Feign

7.1 基于Feign远程调用 RestTimeplate方式调用存在的问题 先来看以前利用RestTemplate发起远程调用的代码&#xff1a; String url "http://userservice/user"order.getUserId(); User user restTemplate.getForObject(url,User.class);存在下面的问题&#xf…...

【Spring Boot 源码学习】OnWebApplicationCondition 详解

Spring Boot 源码学习系列 OnWebApplicationCondition 详解 引言往期内容主要内容1. getOutcomes 方法2. getMatchOutcome 方法3. isWebApplication 方法3.1 isServletWebApplication 方法3.2 isReactiveWebApplication 方法3.3 isAnyWebApplication 方法 总结 引言 上篇博文带…...

力扣之二分法

今天&#xff0c;学习了二分法&#xff0c;详细内容见代码随想录 (programmercarl.com)&#xff0c;讲得十分好。 力扣之35. 搜索插入位置 - 力扣&#xff08;LeetCode&#xff09;。 class Solution { public:int searchInsert(vector<int>& nums, int target) {in…...

css图形化理解--扭曲函数skew()

transform: skewX(30deg);transform: skewY(45deg);transform: skew(30deg,45deg);transform: skewX(angleX);transform: skewY(angleY);transform: skew(angleX,angleY); 是CSS中的一个2D变换方法&#xff0c;它用于对元素沿X轴、Y轴进行倾斜变换。其中&#xff0c;angle表示倾…...

八、互联网技术——物联网

文章目录 一、智慧物联案例分析二、M2M技术三、数据保护综合案例分析一、智慧物联案例分析 智能物流是一种典型的物联网应用。一个物流仓储管理系统架构如下图所示: [问题1] 图中的三层功能:仓库物品识别、网络接入、物流管理中心,分别可对应到物联网基本架构中的哪一层? …...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...