当前位置: 首页 > 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安装完…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...