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排序算法之堆排序
图解 堆排序是一种常见的排序算法,它借助了堆这种数据结构。堆是一种完全二叉树,它可以分为两种类型:最大堆和最小堆。在最大堆中,每个结点的值都大于等于它的子结点的值,而在最小堆中,每个结点的值都小于等…...
『GitHub项目圈选02』一款可实现视频自动翻译配音为其他语言的开源项目
🔥🔥🔥本周GitHub项目圈选****: 主要包含视频翻译、正则填字游戏、敏感词检测、聊天机器人框架、AI 换脸、分布式数据集成平台等热点项目。 1、pyvideotrans pyvideotrans 是一个视频翻译工具,可将一种语言的视频翻译为另一种语…...
Unity - Cinemachine
动态获取Cinemachine的内部组件 vCam.GetCinemachineComponent<T>() 动态修改Cinemachine的Transposer属性 var vCamComp transfrom.GetComponent<CinemachineVirtualCamera>(); var transposerComp vCamComp.GetCinemachineComponent<CinemachineTransposer&…...
准备搞OpenStack了,先装一台最新的Ubuntu 23.10
正文共:1113 字 25 图,预估阅读时间:2 分钟 依稀记得前面发了一篇Ubuntu的安装文档(66%的经验丰富开发者和69%的学生更喜欢的Ubuntu的安装初体验),当时安装的是20.04.3的版本,现在看来已经是非常…...
Android 12 客制化修改初探-Launcher/Settings/Bootanimation
Android 12 使用 Material You 打造的全新系统界面,富有表现力、活力和个性。使用重新设计的微件、AppSearch、游戏模式和新的编解码器扩展您的应用。支持隐私信息中心和大致位置等新的保护功能。使用富媒体内容插入功能、更简便的模糊处理功能、经过改进的原生调试…...
【JavaEE初阶】 HTML基础详解
文章目录 🎋什么是HTML?🍀HTML 结构🚩认识标签🚩HTML 文件基本结构🚩快速生成代码框架 🎄HTML 常见标签🚩注释标签🚩标题标签: h1-h6🚩段落标签: pǶ…...
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图的原理是检验实际累积概率分布与理论累积概率分布是否吻合。若吻合…...
浅尝:iOS的CoreGraphics和Flutter的Canvas
iOS的CoreGraphic 基本就是创建一个自定义的UIView,然后重写drawRect方法,在此方法里使用UIGraphicsGetCurrentContext()来绘制目标图形和样式 #import <UIKit/UIKit.h>interface MyGraphicView : UIView endimplementation MyGraphicView// Onl…...
网络安全黑客技术自学
前言 一、什么是网络安全 网络安全可以基于攻击和防御视角来分类,我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术,而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 无论网络、Web、移动、桌面、云等哪个领域,都有攻与防…...
【文件读取/包含】任意文件读取漏洞 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关键字。 一、单例模式 设计模式是在大量的实践中总结和理论化之后优选的代码结构、编程风格、以及解决问题的思考方式。就像是经典的棋谱,不同的棋局,我…...
深入Android S(12.0) 探索 Android Framework 之 SystemServer 进程启动详解
深入学习 Android Framework 第三:深入Android S(12.0) 探索 Android Framework 之 SystemServer 进程启动详解 文章目录 深入学习 Android Framework前言一、Android 系统的启动流程1. 流程图2. 启动流程概述 二、源码详解1. 时序图2. 源代码1、ZygoteInit # main…...
搜维尔科技:【软件篇】TechViz是一款专为工程设计的专业级3D可视化软件
在沉浸式房间内深入研究您自己的 3D 数据 沉浸式房间是一个交互式虚拟现实空间,其中每个表面(墙壁、地板和天花板)都充当投影屏幕,创造高度沉浸式的体验。这就像您的 3D 模型有一个窗口,您可以在其中从不同角度走动、…...
android Handler
一、Handler的作用 1、Handler的作用是在andorid中实现线程间的通信。我们常说的说的,子线程处理逻辑,主线程更新UI是上述情况的一个子集。 二、源码分析 1、Handler源码 源码地址:http://androidxref.com/7.1.1_r6/xref/frameworks/base/co…...
【Ubuntu·系统·的Linux环境变量配置方法最全】
文章目录 概要读取环境变量的方法小技巧 概要 在Linux环境中,配置环境变量是一种常见的操作,用于指定系统或用户环境中可执行程序的搜索路径。 读取环境变量的方法 在Linux中,可以使用以下两个命令来读取环境变量: export 命令…...
Django之模板层
【1】模板之变量 在Django模板中要想使用变量关键是使用点语法。 获取值的语法是:{{ 变量名 }} Python中所有的数据类型包括函数,类等都可以调用 【2】模板之过滤器 过滤器语法 {{ obj | filter_name:param }} obj:变量名字&…...
社区论坛小程序系统源码+自定义设置+活动奖励 自带流量主 带完整的搭建教程
大家好啊,又到了罗峰来给大家分享好用的源码的时间了。今天罗峰要给大家分享的是一款社区论坛小程序系统。社区论坛已经成为人们交流、学习、分享的重要平台。然而,传统的社区论坛往往功能单一、缺乏个性化设置,无法满足用户多样化的需求。而…...
2023亚太杯数学建模C题思路解析
文章目录 0 赛题思路1 竞赛信息2 竞赛时间3 建模常见问题类型3.1 分类问题3.2 优化问题3.3 预测问题3.4 评价问题 4 建模资料5 最后 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 竞赛信息 2023年第十三…...
acme在同一台服务器上设置多个Ali_key实现自动ssl申请和续期
在同一台服务器上设置多个Ali_key,您可以按照以下步骤进行操作: 首先,确保您已经安装了acme.sh工具。如果没有安装,请先安装acme.sh,您可以使用以下命令安装acme.sh: curl https://get.acme.sh | sh安装完…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
