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

OpenLayers 可视化之热力图

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

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

Springboot 高校报修与互助平台小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;高校报修与互助平台小程序被用户普遍使用&#xff0c;为…...

ubuntu清理垃圾

windows和ubuntu 双系统&#xff0c;ubuntu 150GB&#xff0c;开发用&#xff0c;基本不装太多软件。但是磁盘基本用完。 1、查看home目录 sudo du -h -d 1 $HOME | grep -v K 上面的命令查看$HOME一级目录大小&#xff0c;发现 .cache 有26GB&#xff0c;.local 有几个GB&am…...