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

Java排序算法之堆排序

 图解

        堆排序是一种常见的排序算法,它借助了堆这种数据结构。堆是一种完全二叉树,它可以分为两种类型:最大堆和最小堆。在最大堆中,每个结点的值都大于等于它的子结点的值,而在最小堆中,每个结点的值都小于等于它的子结点的值。

        堆排序的基本思想是:先将待排序的序列构建成一个最大堆(或者最小堆),然后将堆顶元素(最大值或最小值)与序列的最后一个元素交换位置,然后再将剩余的元素重新构建成一个最大堆(或最小堆),继续进行交换和重构堆的操作,直到所有元素都排列好为止。

        堆排序的时间复杂度为O(nlogn),它不仅具有稳定性,而且还适合处理大规模数据的排序问题。

        堆排序是一种基于二叉堆的排序算法,它的时间复杂度为 O(n log n)。

        以下是 Java 实现堆排序的代码:

public class HeapSort {public static void sort(int[] arr) {int n = arr.length;// 建立最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐步取出堆顶元素,放置到数组末尾for (int i = n - 1; i > 0; i--) {swap(arr, 0, i);heapify(arr, i, 0);}}private static void heapify(int[] arr, int n, int i) {int largest = i; // 初始化最大节点为当前节点 iint left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点大于当前节点,则更新最大节点为左子节点if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点大于当前节点和左子节点,则更新最大节点为右子节点if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大节点不是当前节点,则交换它们,再以最大节点为根继续向下堆化if (largest != i) {swap(arr, i, largest);heapify(arr, n, largest);}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

        在上述代码中,sort 方法代表堆排序的入口,它首先建立最大堆,再逐步取出堆顶元素,放置到数组末尾。

  heapify 方法用于维护最大堆的性质,它接受三个参数:数组、数组长度和当前节点的索引。该方法首先找到当前节点的左子节点和右子节点,然后找出它们中的最大值。如果最大值不是当前节点,则交换它们,并以最大节点为根继续向下堆化,直到完成维护最大堆的过程。

  swap 方法用于交换数组中的两个元素。

相关文章:

Java排序算法之堆排序

图解 堆排序是一种常见的排序算法&#xff0c;它借助了堆这种数据结构。堆是一种完全二叉树&#xff0c;它可以分为两种类型&#xff1a;最大堆和最小堆。在最大堆中&#xff0c;每个结点的值都大于等于它的子结点的值&#xff0c;而在最小堆中&#xff0c;每个结点的值都小于等…...

『GitHub项目圈选02』一款可实现视频自动翻译配音为其他语言的开源项目

&#x1f525;&#x1f525;&#x1f525;本周GitHub项目圈选****: 主要包含视频翻译、正则填字游戏、敏感词检测、聊天机器人框架、AI 换脸、分布式数据集成平台等热点项目。 1、pyvideotrans pyvideotrans 是一个视频翻译工具&#xff0c;可将一种语言的视频翻译为另一种语…...

Unity - Cinemachine

动态获取Cinemachine的内部组件 vCam.GetCinemachineComponent<T>() 动态修改Cinemachine的Transposer属性 var vCamComp transfrom.GetComponent<CinemachineVirtualCamera>(); var transposerComp vCamComp.GetCinemachineComponent<CinemachineTransposer&…...

准备搞OpenStack了,先装一台最新的Ubuntu 23.10

正文共&#xff1a;1113 字 25 图&#xff0c;预估阅读时间&#xff1a;2 分钟 依稀记得前面发了一篇Ubuntu的安装文档&#xff08;66%的经验丰富开发者和69%的学生更喜欢的Ubuntu的安装初体验&#xff09;&#xff0c;当时安装的是20.04.3的版本&#xff0c;现在看来已经是非常…...

Android 12 客制化修改初探-Launcher/Settings/Bootanimation

Android 12 使用 Material You 打造的全新系统界面&#xff0c;富有表现力、活力和个性。使用重新设计的微件、AppSearch、游戏模式和新的编解码器扩展您的应用。支持隐私信息中心和大致位置等新的保护功能。使用富媒体内容插入功能、更简便的模糊处理功能、经过改进的原生调试…...

【JavaEE初阶】 HTML基础详解

文章目录 &#x1f38b;什么是HTML&#xff1f;&#x1f340;HTML 结构&#x1f6a9;认识标签&#x1f6a9;HTML 文件基本结构&#x1f6a9;快速生成代码框架 &#x1f384;HTML 常见标签&#x1f6a9;注释标签&#x1f6a9;标题标签: h1-h6&#x1f6a9;段落标签: p&#x1f6…...

C# Socket通信从入门到精通(10)——如何检测两台电脑之间的网络是否通畅

前言: 我们在完成了socket通信程序开发以后,并且IP地址也设置好以后,可以先通过一些手段来测试两台电脑之间的网络是否通畅,如果确认了网络通畅以后,我们再测试我们编写的Socket程序。 1、同时按下键盘的windows键+"R"键,如下图: 下面两张图是两种键盘的情…...

python科研绘图:P-P图与Q-Q图

目录 什么是P-P图与Q-Q图 分位数 百分位数 Q-Q图步骤与原理 Shapiro-Wilk检验 绘制Q-Q图 绘制P-P图 什么是P-P图与Q-Q图 P-P图和Q-Q图都是用于检验样本的概率分布是否服从某种理论分布。 P-P图的原理是检验实际累积概率分布与理论累积概率分布是否吻合。若吻合&#xf…...

浅尝:iOS的CoreGraphics和Flutter的Canvas

iOS的CoreGraphic 基本就是创建一个自定义的UIView&#xff0c;然后重写drawRect方法&#xff0c;在此方法里使用UIGraphicsGetCurrentContext()来绘制目标图形和样式 #import <UIKit/UIKit.h>interface MyGraphicView : UIView endimplementation MyGraphicView// Onl…...

网络安全黑客技术自学

前言 一、什么是网络安全 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 无论网络、Web、移动、桌面、云等哪个领域&#xff0c;都有攻与防…...

【文件读取/包含】任意文件读取漏洞 afr_3

1.1漏洞描述 漏洞名称任意文件读取漏洞 afr_3漏洞类型文件读取/包含漏洞等级⭐⭐⭐⭐⭐漏洞环境docker攻击方式 1.2漏洞等级 高危 1.3影响版本 暂无 1.4漏洞复现 1.4.1.基础环境 靶场docker工具BurpSuite 1.4.2.环境搭建 1.创建docker-compose.yml文件 version: 3.2 servi…...

第四章:单例模式与final

系列文章目录 文章目录 系列文章目录前言一、单例模式二、final 关键字总结 前言 单例模式与final关键字。 一、单例模式 设计模式是在大量的实践中总结和理论化之后优选的代码结构、编程风格、以及解决问题的思考方式。就像是经典的棋谱&#xff0c;不同的棋局&#xff0c;我…...

深入Android S(12.0) 探索 Android Framework 之 SystemServer 进程启动详解

深入学习 Android Framework 第三&#xff1a;深入Android S(12.0) 探索 Android Framework 之 SystemServer 进程启动详解 文章目录 深入学习 Android Framework前言一、Android 系统的启动流程1. 流程图2. 启动流程概述 二、源码详解1. 时序图2. 源代码1、ZygoteInit # main…...

搜维尔科技:【软件篇】TechViz是一款专为工程设计的专业级3D可视化软件

在沉浸式房间内深入研究您自己的 3D 数据 沉浸式房间是一个交互式虚拟现实空间&#xff0c;其中每个表面&#xff08;墙壁、地板和天花板&#xff09;都充当投影屏幕&#xff0c;创造高度沉浸式的体验。这就像您的 3D 模型有一个窗口&#xff0c;您可以在其中从不同角度走动、…...

android Handler

一、Handler的作用 1、Handler的作用是在andorid中实现线程间的通信。我们常说的说的&#xff0c;子线程处理逻辑&#xff0c;主线程更新UI是上述情况的一个子集。 二、源码分析 1、Handler源码 源码地址&#xff1a;http://androidxref.com/7.1.1_r6/xref/frameworks/base/co…...

【Ubuntu·系统·的Linux环境变量配置方法最全】

文章目录 概要读取环境变量的方法小技巧 概要 在Linux环境中&#xff0c;配置环境变量是一种常见的操作&#xff0c;用于指定系统或用户环境中可执行程序的搜索路径。 读取环境变量的方法 在Linux中&#xff0c;可以使用以下两个命令来读取环境变量&#xff1a; export 命令…...

Django之模板层

【1】模板之变量 在Django模板中要想使用变量关键是使用点语法。 获取值的语法是&#xff1a;{{ 变量名 }} Python中所有的数据类型包括函数&#xff0c;类等都可以调用 【2】模板之过滤器 过滤器语法 {{ obj | filter_name&#xff1a;param }} obj&#xff1a;变量名字&…...

社区论坛小程序系统源码+自定义设置+活动奖励 自带流量主 带完整的搭建教程

大家好啊&#xff0c;又到了罗峰来给大家分享好用的源码的时间了。今天罗峰要给大家分享的是一款社区论坛小程序系统。社区论坛已经成为人们交流、学习、分享的重要平台。然而&#xff0c;传统的社区论坛往往功能单一、缺乏个性化设置&#xff0c;无法满足用户多样化的需求。而…...

2023亚太杯数学建模C题思路解析

文章目录 0 赛题思路1 竞赛信息2 竞赛时间3 建模常见问题类型3.1 分类问题3.2 优化问题3.3 预测问题3.4 评价问题 4 建模资料5 最后 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 竞赛信息 2023年第十三…...

acme在同一台服务器上设置多个Ali_key实现自动ssl申请和续期

在同一台服务器上设置多个Ali_key&#xff0c;您可以按照以下步骤进行操作&#xff1a; 首先&#xff0c;确保您已经安装了acme.sh工具。如果没有安装&#xff0c;请先安装acme.sh&#xff0c;您可以使用以下命令安装acme.sh&#xff1a; curl https://get.acme.sh | sh安装完…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

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…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...