【java实现+4种变体完整例子】排序算法中【堆排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格
以下是堆排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：
一、堆排序基础实现
原理
基于二叉堆结构（最大堆），通过以下步骤实现排序：
- 构建最大堆：将数组调整为一个最大堆，根节点为最大值。
- 提取最大值：将堆顶元素（最大值）与末尾元素交换，缩小堆范围，重新调整堆。
- 重复步骤2：直到堆为空。
代码示例
public class HeapSort {void sort(int[] arr) {int n = arr.length;// Build max heapfor (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// Extract elements one by onefor (int i = n - 1; i >= 0; i--) {// Move current root to endint temp = arr[0];arr[0] = arr[i];arr[i] = temp;// Heapify the reduced heapheapify(arr, i, 0);}}// Recursive heapify to build a max heapprivate void heapify(int[] arr, int n, int i) {int largest = i; // Initialize largest as rootint left = 2 * i + 1;int right = 2 * i + 2;// If left child is larger than rootif (left < n && arr[left] > arr[largest]) {largest = left;}// If right child is larger than largest so farif (right < n && arr[right] > arr[largest]) {largest = right;}// If largest is not rootif (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;// Recursively heapify the affected sub-treeheapify(arr, n, largest);}}
}
复杂度分析
- 时间复杂度：
O(n log n)（所有情况）。 - 空间复杂度：
O(log n)（递归调用栈空间）。 - 稳定性：不稳定（相同值的元素可能因交换顺序改变相对位置）。
二、常见变体及代码示例
1. 迭代实现（非递归）
改进点：用循环替代递归，减少栈空间开销。
适用场景：避免递归深度限制或优化性能。
public class IterativeHeapSort {void sort(int[] arr) {int n = arr.length;// Build max heapfor (int i = n / 2 - 1; i >= 0; i--) {iterativeHeapify(arr, n, i);}// Extract elements one by onefor (int i = n - 1; i >= 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;iterativeHeapify(arr, i, 0);}}// Iterative heapify to build a max heapprivate void iterativeHeapify(int[] arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;while (true) {if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}if (largest == i) break;// Swap and continueint swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;i = largest;left = 2 * i + 1;right = 2 * i + 2;}}
}
2. 最小堆实现
改进点：使用最小堆实现排序，需反转结果。
适用场景：需用最小堆结构的场景（如优先队列）。
public class MinHeapSort {void sort(int[] arr) {int n = arr.length;// Build min heapfor (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// Extract elements one by one (ascending order requires reversal)for (int i = n - 1; i >= 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}reverse(arr); // Reverse to get ascending order}// Heapify for min heapprivate void heapify(int[] arr, int n, int i) {int smallest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] < arr[smallest]) {smallest = left;}if (right < n && arr[right] < arr[smallest]) {smallest = right;}if (smallest != i) {swap(arr, i, smallest);heapify(arr, n, smallest);}}private void reverse(int[] arr) {int left = 0, right = arr.length - 1;while (left < right) {swap(arr, left, right);left++;right--;}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
3. 原地堆排序优化
改进点：减少比较次数，优化堆调整过程。
适用场景：追求极致性能的场景。
public class OptimizedHeapSort {void sort(int[] arr) {int n = arr.length;// Build max heap with reduced comparisonsfor (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// Extract elements one by onefor (int i = n - 1; i >= 0; i--) {swap(arr, 0, i);heapify(arr, i, 0);}}// Optimized heapify to reduce comparisonsprivate void heapify(int[] arr, int n, int i) {while (true) {int largest = i;int 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) break;swap(arr, i, largest);i = largest;}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
三、变体对比表格
| 变体名称 | 时间复杂度 | 空间复杂度 | 稳定性 | 主要特点 | 适用场景 |
|---|---|---|---|---|---|
| 基础堆排序（递归） | O(n log n) | O(log n) | 不稳定 | 递归实现，简单直观 | 通用排序，需避免栈溢出时需迭代版 |
| 迭代堆排序 | O(n log n) | O(1) | 不稳定 | 无递归，减少栈空间开销 | 需避免递归深度限制的场景 |
| 最小堆实现 | O(n log n) | O(1) | 不稳定 | 使用最小堆并反转结果，适合特定需求 | 需最小堆结构或特殊排序需求 |
| 原地优化堆排序 | O(n log n) | O(1) | 不稳定 | 减少比较次数，提升性能 | 高性能要求场景 |
四、关键选择原则
- 基础场景：优先使用基础递归实现，因其简单易懂。
- 栈限制场景：迭代实现适合避免递归深度限制（如超大数组）。
- 最小堆需求：最小堆变体适用于需要最小堆结构的场景，但需额外反转步骤。
- 性能优化：原地优化版通过减少比较次数提升效率，适合对性能敏感的场景。
- 稳定性需求：所有变体均不稳定，若需稳定排序需选择其他算法（如归并排序）。
通过选择合适的变体，可在特定场景下优化性能或适应硬件限制。例如，迭代实现避免栈溢出，而原地优化版通过减少比较次数提升效率。
相关文章：
【java实现+4种变体完整例子】排序算法中【堆排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格
以下是堆排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格： 一、堆排序基础实现 原理 基于二叉堆结构（最大堆），通过以下步骤实现排序： 构建最大堆：将…...
量化交易 - RSRS（阻力支撑相对强度）策略研究 - 源码
一、介绍 RSRS（阻力支撑相对强度）是一种基于价格阻力位与支撑位动态变化的市场择时技术指标，由光大证券在2017年提出。其核心原理是通过量化最高价与最低价之间的线性关系，预测市场趋势变化。 原理： 线性回归建模&a…...
从FPGA实现角度介绍DP_Main_link主通道原理
DisplayPort（简称DP）是一个标准化的数字式视频接口标准，具有三大基本架构包含影音传输的主要通道（Main Link）、辅助通道（AUX）、与热插拔（HPD）。 Main Link：用…...
数据库备份-docker配置主从数据库
创建 Docker Compose 文件 创建一个 docker-compose.yml 文件，定义两个 MySQL 容器（一个主库，一个从库） services:mysql:image: mysql:8.0.27container_name: mysqlports:- "3306:3306"environment:TZ: Asia/ShanghaiM…...
YOLO11改进-Backbone-使用MobileMamba替换YOLO backbone 提高检测精度
轻量化模型的技术瓶颈 CNN 的局限性：传统 CNN（如 MobileNet）依赖局部感受野，难以捕捉长距离依赖关系，在高分辨率任务（如语义分割）中需通过增加计算量提升性能，效率低下。 Transforme…...
JavaScript学习教程，从入门到精通，DOM 操作语法知识点及案例代码（20）
DOM 操作语法知识点及案例代码 一、DOM 介绍 1. 什么是 DOM DOM (Document Object Model，文档对象模型) 是 HTML 和 XML 文档的编程接口。它提供了对文档的结构化的表示，并定义了一种方式可以使从程序中对该结构进行访问，从而改变文档的结…...
Vue3 + TypeScript中defineEmits 类型定义解析
TypeScript 中 Vue 3 的 defineEmits 函数的类型定义，用于声明组件可以触发的事件。以下是分步解释： 1. 泛型定义 ts <"closeDialog" | "getApplySampleAndItemX"> 作用：定义允许的事件名称集合，即组…...
Git命令归纳
初始化git git config --global user.name xxx：设置全局用户名，信息记录在~/.gitconfig文件中git config --global user.email xxxxxx.com：设置全局邮箱地址，信息记录在~/.gitconfig文件中git init：先创建一个目录&am…...
Oracle Recovery Tools修复ORA-600 6101/kdxlin:psno out of range故障
数据库异常断电,然后启动异常,我接手该库,尝试recover恢复 SQL> recover database; ORA-10562: Error occurred while applying redo to data block (file# 2, block# 63710) ORA-10564: tablespace SYSAUX ORA-01110: ???????? 2: H:\TEMP\GDLISNET\SYSAUX01.DBF O…...
ISO26262-浅谈用例导出方法和测试方法
目录 1 摘要2 测试方法3 测试用例导出方法4 测试方法与用例导出方法的差异和联系5 结论 1 摘要 ISO26262定义了测试方法和用例导出方法，共同保证产品的开发质量。但在刚开始学习ISO26262的时候，又不是非常清晰地理解它俩的区别和联系。本文主要对它俩的…...
小测验——已经能利用数据集里面的相机外参调整后看到渲染图像
文章目录 .1 外try——牛的显示.2 try——衣服的显示.3 原生R，T但是部分显示.4 在.3的基础上加上可视化界面.5 调参后能看到东西的.6 能看一点东西+可视化（pytorch3d）.7 自己的代码可视化——需要调整.1 外try——牛的显示 import numpy as np import matplotlib.pyplot as …...
2024期刊综述论文 Knowledge Graphs and Semantic Web Tools in Cyber Threat Intelligence
发表在期刊Journal of Cybersecurity and Privacy上，专门讲知识图谱技术和语义Web工具在网络威胁情报领域的作用，还把本体和知识图谱放在相同的地位上讨论。 此处可以明确一点：本体和知识图谱都可以用于网络威胁情报的应用，当然也…...
文件上传及验证绕过漏洞
目录 一、文件上传常见点 二、客户端--JS绕过--PASS-01 1、环境安装 2、禁用JS 3、后缀名绕过 4、修改前端代码 三、服务端黑名单绕过 1、特殊可解析后缀--PASS-03 2、大小写绕过--PASS-06 3、点绕过--PASS-08 4、空格绕过--PASS-07 5、::$DATA绕过--PASS-09 6、配…...
stack和queue的使用和模拟实现
1：stack文档 stack文档 stack的使用 2：queue文档 queue文档 queue的使用 1：队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。 2：队列作…...
基于Ubuntu2504部署OpenStack E版
OpenStack 初始化环境安装数据库、memcahe、rabbitmq等服务安装keystone服务安装glance服务安装placement服务安装nova服务安装neutron服务安装horizon服务 官网 OpenStack Epoxy 巩固了作为 VMware 替代方案的地位，增强了安全性，并改进了硬件支持 第 3…...
Jsp技术入门指南【七】JSP动作讲解
Jsp技术入门指南【七】JSP动作讲解 前言一、什么是JSP动作？二、核心JSP动作详解1. jsp:include：动态包含其他页面与<% include %>的区别 2. jsp:forward：请求转发到另一个页面3. jsp:param：为动作传递参数4. jsp:useBean&am…...
电脑 访问 github提示 找不到网页，处理方案
1、找到 本机的 host文件 例如 windows 的 一般在 C:\Windows\System32\drivers\etc\hosts 用管理员身份打开 hosts 文件 如果文件中没有 github的配置，需要自己手动添加上去； 如果有，则需要 检查 github.com 与 github.global.ssl.fastly.…...
性能比拼: Elixir vs Go
本内容是对知名性能评测博主 Anton Putra Elixir vs Go (Golang) Performance (Latency - Throughput - Saturation - Availability) 内容的翻译与整理, 有适当删减, 相关指标和结论以原作为准 对比 Elixir 和 Go 简介 许多人长期以来一直要求我对比 Elixir 和 Go。在本视频…...
){kind=spacer}
动手实现文本生成模型：基于 Decoder-only Transformer (PyTorch)
1. 选择框架：PyTorch 我们选择 PyTorch 作为实现框架。PyTorch 提供了灵活的动态图，并且拥有功能强大的 nn.Transformer 模块，方便我们快速构建模型。其社区活跃，资源丰富，是进行深度学习研究和开发的优秀选择。 确保你已经安装了 PyTorch 和其他必要的库： Bash pip i…...
WSL+Ubuntu+miniconda环境配置
安装到指定目录 bash Miniconda3-latest-Linux-x86_64.sh -b -p /usr/local/miniconda3添加环境变量 echo export PATH"/usr/local/miniconda3/bin:$PATH" >> /etc/profile echo export PATH"/usr/local/miniconda3/bin:$PATH" >> ~/.bashrc…...
linux学习 5 正则表达式及通配符
重心应该放在通配符的使用上 正则表达式 正则表达式是用于 文本匹配和替换 的强大工具 介绍两个交互式的网站来学习正则表达式 regexlearn 支持中文 regexone 还有一个在线测试的网址 regex101 基本规则 符号作用示例.匹配任何字符除了换行a.b -> axb/a,b[abc]匹配字符…...
【web服务_负载均衡Nginx】三、Nginx 实践应用与高级配置技巧
一、Nginx 在 Web 服务器场景中的深度应用 1.1 静态网站部署与优化 在 CentOS 7 系统中，使用 Nginx 部署静态网站是最基础也最常见的应用场景。首先，准备网站文件，在/var/www/html目录下创建index.html文件： sudo mkdir -p…...
详解与HTTP服务器相关操作
HTTP 服务器是一种遵循超文本传输协议（HTTP）的服务器，用于在网络上传输和处理网页及其他相关资源。以下是关于它的详细介绍： 工作原理 HTTP 服务器监听指定端口（通常是 80 端口用于 HTTP，443 端口用于 HT…...
LeetCode 2563.统计公平数对的数目：排序 + 二分查找
【LetMeFly】2563.统计公平数对的数目：排序 二分查找 力扣题目链接：https://leetcode.cn/problems/count-the-number-of-fair-pairs/ 给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平…...
Manus技术架构、实现内幕及分布式智能体项目实战
Manus技术架构、实现内幕及分布式智能体项目实战 模块一： 剖析Manus分布式多智能体全生命周期、九大核心模块及MCP协议，构建低幻觉、高效且具备动态失败处理能力的Manus系统。 模块二： 解析Manus大模型Agent操作电脑的原理与关键API…...
基于springboot的个人财务管理系统的设计与实现
博主介绍：java高级开发，从事互联网行业六年，熟悉各种主流语言，精通java、python、php、爬虫、web开发，已经做了六年的毕业设计程序开发，开发过上千套毕业设计程序，没有什么华丽的语言࿰…...
新能源汽车动力电池热管理方案全解析：开启电车续航与安全的密码
热管理：新能源汽车的隐形守护者 在新能源汽车飞速发展的今天，热管理系统作为保障车辆核心部件稳定运行的关键，正逐渐成为行业关注的焦点。据市场研究机构的数据显示，近年来新能源汽车的销量持续攀升，而与之相伴的是热…...
Ubuntu开启自启动PostgreSQL读取HDD失败处理思路
前置文章： windows通用网线连接ubuntu实现ssh登录、桌面控制、文件共享Ubuntu挂载HDD迁移存储PostgreSQL数据 背景： 启动实体Ubuntu机器后后很大的概率PostgreSQL不会成功启动，查看日志： Ubuntu启动时间： rootPine…...
损失函数总结
目录 回归问题L1损失 平均绝对值误差（MAE）Smooth L1 LossL2损失 均方误差损失MSE 分类问题交叉熵损失KL 散度损失 KLDivLoss负对数似然损失 NLLLoss 排序MarginRankingLoss 回归问题 L1损失 平均绝对值误差（MAE） 指模型预测值f(x…...
LeetCode 热题 100：回溯
46. 全排列 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入：nums [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2： 输入ÿ…...
Jetson Orin NX 部署YOLOv12笔记
步骤一.创建虚拟环境 conda create -n yolov12 python3.8.20 注意：YOLOv12/YOLOv11/YOLOv10/YOLOv9/YOLOv8/YOLOv7a/YOLOv5 环境通用 步骤二.激活虚拟环境 conda activate yolov12 #激活环境 步骤三.查询Jetpack出厂版本 Jetson系列平台各型号支持的最高Jetp…...
『Linux_网络』 第二章 UDP_Socket编程
学习了网络的概念了，接下来我们开始实践，本次我们会通过UDP来模拟实现UDP客户端和UDP服务器之间的通信，以及在此基础上扩展几个应用。 下面，我们将使用socket，bind，htons等接口实现UDP网络通信。 v1 版本 …...
【leetcode刷题日记】lc.322-零钱兑换
目录 1.题目 2.代码 1.题目 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认…...
从GET到POST：HTTP请求的攻防实战与CTF挑战解析
初探HTTP请求：当浏览器遇见服务器 基础协议差异可视化 # 典型GET请求 GET /login.php?username=admin&password=p@ssw0rd HTTP/1.1 Host: example.com User-Agent: Mozilla/5.0# 典型POST请求 POST /login.php HTTP/1.1 Host: example.com Content-Type: application/x…...
实现Azure Data Factory安全地请求企业内部API返回数据
需要配置一个Web Activity组件在Azure云上的Azure Data Factory运行，它需要访问企业内部的API获取JSON格式的数据，企业有网关和防火墙，API有公司的okta身份认证，通过公司的域账号来授权访问，现在需要创建一个专用的域账…...
JDOM处理XML：Java程序员的“乐高积木2.0版“
各位代码建筑师们！今天我们要玩一款比原生DOM更"Java友好"的XML积木套装——JDOM！它像乐高得宝系列（Duplo）一样简单易用，却能让你的XML工程稳如霍格沃茨城堡！（温馨提示：别…...
 PyTorch实现)
Grouped Query Attention (GQA) PyTorch实现
个人在网上看到的实现好像都长得奇奇怪怪的，没有简洁的感觉，因此在这里给出一种易读的GQA实现方法： import torch import torch.nn as nn import torch.nn.functional as Fclass GroupedQueryAttention(nn.Module):def __init__(self, embed…...
《AI大模型应知应会100篇》第27篇：模型温度参数调节：控制创造性与确定性
第27篇：模型温度参数调节：控制创造性与确定性 摘要 在大语言模型的使用中，“温度”（Temperature）是一个关键参数，它决定了模型输出的创造性和确定性之间的平衡。通过调整温度参数，您可以根据任…...
演讲比赛流程管理项目c++
对于一个基本项目，先分析基本的东西有哪些 1.类 演讲管理类:用于编写比赛流程用的功能 演讲者类：包含姓名，分数 创建比赛流程：创建选手12个人，分为两组，6人一组，每组进行两轮比赛࿰…...
在小米AX6000中通过米家控制tailscale
由于tailscale占用内存较大，AX6000中的可用内存非常有限，所以需要对AX6000的内存使用进行优化： 1.减小tmpfs内存占用的大小： #从150M -> 90M，由于tailscale下载安装包是27M作用， 解压后50M左右…...
REC: 引爆全球万亿级市场！Web3+消费革命重塑全球-东南亚-跨境商业未来
在全球数字经济浪潮下，东南亚已成为增长最快的互联网市场之一，其与全球之间蓬勃发展的跨境贸易更是蕴藏着巨大潜力。然而，传统模式下的效率瓶颈、信任壁垒和用户激励难题日益凸显。在此背景下，基于去中心化与消费相结合的 REC 颠覆…...
微服务与事件驱动架构（EDA）
微服务架构 微服务架构核心特征 服务自治：每个服务拥有独立的代码库、数据库和运维流程。轻量级通信：服务间通过API（REST/gRPC）或消息队列（如Kafka）交互。去中心化治理：允许技术栈多样化&…...
单片机如何通过串口与上位机进行数据交换
单片机通过串口与上位机进行数据交换是一种常见的方式，广泛应用于嵌入式系统中。以下是实现这一功能的具体步骤和注意事项： 1. 硬件连接 在硬件层面，需要确保单片机和上位机之间的串口连接正确： 信号线连接：通常使用…...
AI速读 Seed-Thinking-v1.5：大模型推理的新飞跃
在大语言模型（LLM）蓬勃发展的今天，推理模型的性能提升成为了AI领域的关键议题。今天为大家解读的论文，带来了名为Seed-Thinking-v1.5的推理模型，它在多个任务上表现惊艳，还创新性地解决了不少难题ÿ…...
-全面了解增删改查(CRUD).)
Mysql从入门到上手(二)-全面了解增删改查(CRUD).
一、检索数据 MySQL 中的检索数据操作是数据库操作中最常见的任务之一。使用 SQL 查询语言中的 SELECT 语句，可以从数据库中的一个或多个表中检索数据。以下是 MySQL 中与数据检索相关的各种技术和用法的详细讲解。 1.1、基本查询 最基本的查询是使用 SELECT 语句来…...
220V转5V转12V电机驱动供电WT5105
220V转5V转12V电机驱动供电WT5105 WT5105 芯片概述 WT5105 是一款集成非隔离式电源控制器，内部集成了 650V 高雪崩能力功率 MOSFET 以及高压启动与自供电电路。该芯片具有多模式输出的特点，输出电压可通过 FB 电阻灵活调整，能够实现 3.3V 以…...
基于Python Django 的全国房价大数据可视化系统（附源码，部署）
博主介绍：✌程序员徐师兄，7年大厂开发经验。全网粉丝12w，CSDN博客专家，同时活跃在掘金、华为云、阿里云、InfoQ等平台，专注Java技术和毕业项目实战分享✌ 🍅文末获取源码联系🍅 👇&a…...
leetcode0113. 路径总和 II - medium
1 题目：路径总和 II 官方标定难度：中 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1： 输入：root …...
day46——两数之和-输入有序数组（LeetCode-167）
题目描述 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 < index1 < index2 &l…...
数据结构：以一个例题演示弗洛伊德算法
例 8.5.2 利用弗洛伊德算法，对图 8.5.5 中左侧的带权有向图求最短路径，给出每一对顶点之间的最短路径及其路径长度在求解过程中的变化。 图 8.5.5 带权图和邻接矩阵 【解】 根据图 8.5.5 中的带权有向图，可得所对应的邻接矩阵 g g g &#…...