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

二叉树之推排序(升序)

目录

  • 1.思路
    • 1.1大堆的建立方法
    • 1.2排序的方法
  • 2.代码实现以及测试代码

1.思路

如何将一个堆进行排序,并变成升序?首先,如果要完成升序,那我们可以建立一个大堆,因为大堆可以选出一个最大的值放在堆的最上面,我们就可以根据每次选出一个最大值来进行排序的做法.

1.1大堆的建立方法

值得一说的是,如果给定一个数组,让进行建堆排序操作的话,建立大堆可以有两种不同的过程,两种过程对应了不同的时间复杂度
首先第一种:向上调整法

for (int i = 1; i < n; i++)
{AdjustUp(a, i);
}

在这里插入图片描述
如图所示,时间复杂度为:O(N*logN)
另一种方法:向下调整法:
与向上调整法不同的是,向下调整法开始的第一个节点是最后一个非叶子节点
for (int i = (n - 1 - 1) / 2; i >= 0; i–)
{
AdjustDown(a, n, i);
}
在这里插入图片描述
如图所示,时间复杂度为:O(N),

1.2排序的方法

利用大堆的特点,每次选出一个最大值并与最后一个值进行交换,换到最后得到的数组就为排序好的数组.

int end = n - 1;
while (end > 0)
{Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;
}

2.代码实现以及测试代码

实现代码:

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}
void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}}

测试代码:


int main()
{ int a[] = { 4,6,2,1,5,8,2,9 };int size = sizeof(a) / sizeof(int);HeapSort(a, size);for (int i = 0; i < size; i++){printf("%d ", a[i]);}return 0;
}

运行截图:
在这里插入图片描述

结尾:今天的分享到此结束,喜欢的朋友如果感觉有帮助可以点赞三连支持,咱们共同进步!

相关文章:

二叉树之推排序(升序)

目录 1.思路1.1大堆的建立方法1.2排序的方法 2.代码实现以及测试代码 1.思路 如何将一个堆进行排序&#xff0c;并变成升序&#xff1f;首先&#xff0c;如果要完成升序&#xff0c;那我们可以建立一个大堆&#xff0c;因为大堆可以选出一个最大的值放在堆的最上面&#xff0c…...

【Docker项目实战】使用Docker部署Plik临时文件上传系统

【Docker实战项目】使用Docker部署Plik 临时文件上传系统 一、Plik介绍1.1 Plik简介1.2 Plik特点 二、本地环境介绍2.1 本地环境规划2.2 本次实践介绍 三、本地环境检查3.1 检查Docker服务状态3.2 检查Docker版本3.3 检查docker compose 版本 四、下载Plik镜像五、部署Plik临时…...

JsonRPC协议详解(协议介绍、请求示例、响应示例)

JsonRPC协议详解 文章目录 JsonRPC协议详解什么是RPC&#xff1f;什么是JsonRPC&#xff1f;JsonRPC详解请求示例响应示例成功和失败响应示例参数的数据类型 结束语 什么是RPC&#xff1f; RPC&#xff08;远程过程调用&#xff09;是一种用于实现分布式系统中不同进程或不同计…...

系列六、Spring整合单元测试

一、概述 Spring中获取bean最常见的方式是通过ClassPathXmlApplicationContext 或者 AnnotationConfigApplicationContext的getBean()方式获取bean&#xff0c;那么在Spring中如何像在SpringBoot中直接一个类上添加个SpringBootTest注解&#xff0c;即可在类中注入自己想要测试…...

如何把 Oracle 19C RAC+DG加入到ORACLE EM 13C监控

平时见ORACLE 19c rac single dg的部署很多了&#xff0c;ORACLE em 13c 的安装也很多了,但如何把手工部署的oracle 19c rac dg 添加到em 13c 中去&#xff0c;让EM13C 来实现对RACDG的监控&#xff0c;主要是DG的EM13C的监控&#xff0c;还没有看到&#xff0c;大部分都是直接…...

Go 编程语言详解:用途、特性、与 Python 和 C++ 的比较

什么是Go? Go是一个跨平台、开源的编程语言Go可用于创建高性能应用程序Go是一种快速、静态类型、编译型语言&#xff0c;感觉上像动态类型、解释型语言Go由Robert Griesemer、Rob Pike和Ken Thompson于2007年在Google开发Go的语法类似于C Go用于什么&#xff1f; Web开发&…...

后缀数组

后缀数组感觉有点不好解释&#xff0c;简单记录一下板子。 后缀数组性质 lcp(i, j):指的是第i个后缀以及第j个后缀的最大公共前缀的长度 lcp(i, j) lcp(j, i) lcp(i, i) len(i) lcp(i, j) min(lcp(i, k), lcp(k, j)) 在o(nlogn)的时间复杂度内处理一个字符串&#xff…...

矩阵的初等变换

1.矩阵的初等变换的分类&#xff1a; 1.按类型分&#xff1a;初等行变换&#xff08;动行&#xff09;&#xff0c;初等列变换&#xff08;动列&#xff09; 2.按方式分&#xff1a; 1.交换矩阵的两行或者两列 2.用一个不为0的数乘矩阵的某一行 3.用一个任意的数乘矩阵的某一行…...

Redis面试题:分片集群相关问题

目录 面试官&#xff1a;redis的分片集群有什么作用 面试官&#xff1a;Redis分片集群中数据是怎么存储和读取的&#xff1f; 面试官&#xff1a;redis的分片集群有什么作用 候选人&#xff1a;分片集群主要解决的是&#xff0c;海量数据存储的问题&#xff0c;集群中有多个m…...

leetcode设计循环队列(链表方式来实现)

上次我们那个设计循环队列的时候用的是数组&#xff0c;因为那个时候还是不太会链表&#xff0c;现在有了链表的思路&#xff0c;我们一起来看看解题步骤吧。 https://leetcode.cn/problems/design-circular-queue/description/ 设计循环队列 那我们其实最主要的就是我们这个…...

什么是高级语言、机器语言、汇编语言?什么是编译和解释?

1、高级语言 计算机程序是一种让计算机执行特定任务的方法。程序是由程序员用一种称为编程语言的特殊语言编写的。编程语言有很多种&#xff0c;例如 C、C、Java、Python 等。这些语言被称为高级语言&#xff0c;因为它们更接近人类的自然语言&#xff0c;而不是计算机能够直接…...

简要介绍Spring原生框架与Spring是轻量级框架的原因

&#x1f609;&#x1f609; 学习交流群&#xff1a; ✅✅1&#xff1a;这是孙哥suns给大家的福利&#xff01; ✨✨2&#xff1a;我们免费分享Netty、Dubbo、k8s、Mybatis、Spring...应用和源码级别的视频资料 &#x1f96d;&#x1f96d;3&#xff1a;QQ群&#xff1a;583783…...

成为AI产品经理——AI产品经理工作全流程

目录 一、业务背景 二、产品工作流程 1.需求定义 2.技术预研 3.数据准备 4.模型构建、宣讲和验收 5.工程开发及产品上线运营 一、业务背景 背景&#xff1a;排球日常训练活动、排球中考项目和排球体测项目耗费了大量人力成本和时间成本。 目标&#xff1a;开发一套用…...

git commit 撤销的三种方法

一般在提交代码的时候&#xff0c;顺序是这样的 git status // 查看修改文件状态&#xff08;已添加至暂存区还是未添加至暂存区&#xff09;git add . // 添加所有已修改文件 git add xxx/xxx // 添加目录为xxx/xxx的文件至暂存区git commit -m xx功能全部完成 // 提交暂存区…...

Linux系统编程 day06 进程间通信

进程间通信 1. 进程间通信的概念2. 匿名管道pipe3. 命名管道FIFO4. 内存映射区 1. 进程间通信的概念 在Linux的环境下&#xff0c;进程地址空间是相互独立的&#xff0c;每个进程有着各自不同的用户地址空间。一个进程不能访问另一个进程中的内容&#xff0c;要进行数据交换必…...

血的教训--redis被入侵之漏洞利用复现--总览

血的教训–redis被入侵之漏洞利用复现–总览 相信大家对于自己的服务器被入侵&#xff0c;还是比较憎恨的&#xff0c;我的就被攻击了一次&#xff0c;总结经验&#xff0c;自己也是整理了这一个系列&#xff0c;从最基础到最后面的自己总结被攻破的步骤&#xff0c;非常清晰的…...

C语言矩阵乘积(ZZULIOJ1127:矩阵乘积)

题目描述 计算两个矩阵A和B的乘积。 输入第一行三个正整数m、p和n&#xff0c;0<m,n,p<10&#xff0c;表示矩阵A是m行p列&#xff0c;矩阵B是p行n列&#xff1b;接下来的m行是矩阵A的内容&#xff0c;每行p个整数&#xff0c;用空格隔开&#xff1b;最后的p行是矩阵B的内…...

用windows自带的FTP服务器实现同一局域网建立ftp服务器实现文件共享的详细步骤

原理 Windows自带的FTP服务器是Internet Information Services&#xff08;IIS&#xff09;组件的一部分&#xff0c;可以用于同一局域网建立FTP服务器以实现文件共享。下面是使用Windows自带的FTP服务器实现文件共享的详细步骤&#xff1a; 安装IIS组件&#xff1a; 打开控制…...

SpringBoot——模板引擎及原理

优质博文&#xff1a;IT-BLOG-CN 一、模板引擎的思想 模板是为了将显示与数据分离&#xff0c;模板技术多种多样&#xff0c;但其本质都是将模板文件和数据通过模板引擎生成最终的HTML代码。 二、SpringBoot模板引擎 SpringBoot推荐的模板引擎是Thymeleaf语法简单&#xff0…...

java开发中各个环境的适用场景

java开发中各个环境的适用场景 一.开发环境 在系统开发的经典模型&#xff0c;一般会分成 2 类 5 种环境&#xff1a; 【线下】本地环境(local)、开发环境(dev)、测试环境(test) 【线上】预发布环境(stage)、生产环境(prod) 每个环境、每个项目使用独立的二级域名 线下、线…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...