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

数据结构-堆排序Java实现

目录

  • 一、引言
  • 二、算法步骤
  • 三、原理演示
    • 步骤1: 构建最大堆
    • 步骤2: 交换和堆化
    • 步骤3: 排序完成
  • 四、代码实战
  • 五、结论

一、引言

    堆排序是一种利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

二、算法步骤

堆排序的核心是建立和维护一个二叉堆,通常是一个最大堆(Max Heap)或最小堆(Min Heap)。在最大堆中,根节点的值是最大的,而在最小堆中,根节点的值是最小的。堆排序的基本思路如下:

  1. 构建最大堆:将未排序的数组构建成一个最大堆。这通常需要从最后一个非叶子节点开始,逐步向前调整,使整个数组满足最大堆的性质。
  2. 交换和堆化:将最大堆的根节点与最后一个元素交换,然后减小堆的大小(即排除最后一个元素),再对根节点进行堆化操作,以保持最大堆的性质。
  3. 重复步骤2:重复执行步骤2,直到堆的大小减小到1,排序完成。

三、原理演示

堆排序是一种基于二叉堆数据结构的排序算法,它通过构建和维护一个最大堆(或最小堆)来对数组进行排序。在这里,我将动态说明堆排序的实现过程,以帮助您更好地理解它。

步骤1: 构建最大堆

假设我们有一个未排序的整数数组作为输入。第一步是将这个数组构建成一个最大堆,确保堆的性质:每个父节点的值都大于或等于其子节点的值。初始数组:
[4, 10, 3, 5, 1]
构建最大堆的过程:
从数组的中间元素开始,即索引为 n/2 - 1,这是最后一个非叶子节点。从这个节点向前遍历,执行堆化操作。
[4, 10, 3, 5, 1]
堆化过程:从根节点开始,比较它与其子节点的值,如果子节点的值更大,则交换它们,然后继续堆化子节点。
[10, 4, 3, 5, 1]
继续堆化直到整个数组成为最大堆。

步骤2: 交换和堆化

在第一步完成后,我们已经构建了一个最大堆,其中根节点包含最大的元素。现在,我们将根节点与最后一个元素交换,将最大元素放到正确的位置。交换和堆化的过程:
交换根节点和最后一个元素:
[1, 4, 3, 5, 10]
减小堆的大小,排除最后一个元素。
对根节点进行堆化操作,以保持最大堆性质。
[5, 4, 3, 1]
重复步骤1和步骤2,直到堆的大小减小到1,排序完成。

步骤3: 排序完成

最终,堆排序完成,数组中的元素按升序排列。
排序完成的数组:
[1, 3, 4, 5, 10]
这就是堆排序的整个过程。它的时间复杂度为O(nlogn),具有稳定性,适用于大型数据集的排序。堆排序的核心是构建和维护堆,确保最大(或最小)元素位于根节点,然后将根节点与数组末尾的元素交换,并逐渐减小堆的大小。

四、代码实战

下面我们使用java演示一下堆排序的过程:

public class HeapSort {public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6, 7};int n = arr.length;System.out.println("原始数组:");printArray(arr);heapSort(arr);System.out.println("排序后的数组:");printArray(arr);}public static void heapSort(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--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}}public static void heapify(int[] arr, int n, int i) {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) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}}public static void printArray(int[] arr) {for (int value : arr) {System.out.print(value + " ");}System.out.println();}
}

上述代码演示了堆排序的实现。它首先定义了一个包含整数数组的示例,然后调用 heapSort 方法来对数组进行排序。heapSort 方法首先构建一个最大堆,然后进行排序。heapify 方法用于维护最大堆的性质。

五、结论

我们一起来总结一下:

  1. 堆排序是一种选择排序的变种,它将待排序序列划分成若干个子序列,每个子序列都满足堆积的性质,即子序列的最大值(或最小值)位于其顶部。
  2. 堆排序的时间复杂度为O(nlogn),其中n表示待排序序列的长度。这是因为堆排序需要将序列构造成堆,这需要O(nlogn)的时间复杂度,然后需要依次取出每个元素,这需要O(n)的时间复杂度。
  3. 堆排序的空间复杂度为O(1)。这是因为堆排序只需要在内存中使用常数级别的额外空间来完成排序。
  4. 堆排序是原地排序算法,也就是说,它不需要额外的存储空间,除了用于存储待排序序列本身的存储空间之外。
  5. 堆排序是稳定的排序算法,也就是说,它保持了相同元素的相对顺序。
  6. 堆排序适用于大规模数据的排序,特别是当内存空间有限时,因为它只需要常数级别的额外空间。
  7. 堆排序算法的实现比较简单,但理解和掌握它需要对数据结构和算法有较深入的理解。
    点赞收藏,富婆包养✋✋

相关文章:

数据结构-堆排序Java实现

目录 一、引言二、算法步骤三、原理演示步骤1: 构建最大堆步骤2: 交换和堆化步骤3: 排序完成 四、代码实战五、结论 一、引言 堆排序是一种利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构&#xff0c;并同时满足堆积的性质&#xff1a;即子结点的键值或…...

C#进阶——反射(Reflection)

定义&#xff1a;反射指的是在运行时动态地获取、检查和操作程序中的类型信息&#xff0c;而在我们的Unity中反射允许开发者在运行时通过代码来访问和修改对象的属性、方法和字段&#xff0c;而不需要提前知道这些成员的具体信息。 举一个例子&#xff0c;我们使用反射在运行的…...

Oracle 运维篇+应用容器数据库的install、upgrade、patch、uninstall

★ 知识点 ※ DEFAULT_SHARING参数的取值 METADATA: 元数据链接共享数据库对象的元数据&#xff0c;但其数据对于每个容器是唯一的。这些数据库对象被称为元数据链接的应用程序公共对象。此设置为默认设置。DATA: 数据链接共享数据库对象&#xff0c;其数据对于应用程序容器中…...

Affinity Publisher for Mac/Windows最新中文下载 排版神器

Affinity Publisher是一款专业的排版和设计软件&#xff0c;它可以帮助您从简单的文档到复杂的书籍和杂志轻松创建高质量的出版物。 该软件具有直观的界面和强大的功能&#xff0c;使您可以轻松组织和编辑文本、图像和数据&#xff0c;并创建令人惊叹的布局。 Affinity Publi…...

Mac文件对比同步工具 Beyond Compare 4.4.7

Beyond Compare 4 是一款强大的文件和文件夹比较工具。它提供了一个直观的界面&#xff0c;使您可以快速比较和同步文件和文件夹。 Beyond Compare 4 具有许多有用的功能&#xff0c;包括比较和合并文件、文件夹和压缩文件&#xff0c;以及同步文件和文件夹。它支持各种类型的文…...

技巧 | 如何解决 OBS 系统声音无法捕获问题 | Mac

技巧 | 如何解决 OBS 系统声音无法捕获问题 | Mac 问题描述 由于 macOS 系统限制&#xff0c;桌面音频被禁止&#xff0c;导致在使用 OBS 无法录制桌面音频&#xff0c;只能使用自带麦克风录制。 解决方法 Loopback 介绍 借助 Loopback 的强大功能&#xff0c;可以轻松地…...

从头开始机器学习:逻辑回归

一、说明 本篇实现线性回归的先决知识是&#xff1a;基本线性代数&#xff0c;微积分&#xff08;偏导数&#xff09;、梯度和、Python &#xff08;NumPy&#xff09;&#xff1b;从线性方程入手&#xff0c;逐渐理解线性回归预测问题。 二、逻辑回归简介 我们将以我们在线性回…...

插入排序 算法

从第二个开始&#xff0c;从后面往前找&#xff0c;如果比其小&#xff0c;就交换&#xff0c;else 就终止 for i 1 i <n i for j i j > 0 (到第二个) j-- if < swap 下面给出源码 //对插入排序来说&#xff0c;直接从第二个元素开始template<ty…...

“揭秘!如何通过京东商品详情接口轻松获取海量精准商品信息!“

京东商品详情接口可以通过HTTP GET请求获取商品详情信息。 请求参数包括num_iid&#xff0c;表示JD商品ID。 请求示例&#xff1a; GET /jd/item_get/?num_iid10335871600 HTTP/1.1 Host: api-vx.Taobaoapi2014.cn Connection: close Accept-Encoding: gzip 点击获取…...

已经有多人中招,不要被AI换脸技术骗了!

您好&#xff0c;我是码农飞哥&#xff08;wei158556&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精…...

solidworks 2024新功能之--保存为低版本 硕迪科技

大家期盼已久的SOLIDWORKS保存低版本文件功能来了&#xff0c;从SOLIDWORKS 2024 开始&#xff0c;您可以将在最新版本的SOLIDWORKS 中创建的SOLIDWORKS零件、装配体和工程图另存为SOLIDWORKS 早期版本的全功能文档&#xff08;完成的特征树与相关参数&#xff09;。 将文件另…...

MySQL --- 聚合查询 和 联合查询

聚合查询&#xff1a; 下文中的所有聚合查询的示例操作都是基于此表&#xff1a; 聚合函数 聚合函数都是行与行之间的运算。 count() select count(列名) from 表名; 统计该表中该列的行数&#xff0c;但是 null 值不会统计在内&#xff0c;但是如果写为 count(*) 那么 nu…...

Note——torch.size() umr_maximum() array.max() itertools.product()

torch.size Problem TypeError: ‘torch.Size’ object is not callable Reason Analysis torch.Size函数不可调用 因为torch只可以.size() 或 shape Solution 将y.shape()替换为y.size() 或 y.shape ytorch.normal(0,0.01,y.size())2 return umr_maximum(a, axis, None…...

python学习笔记6-DefaultDict

对于一般的字典来说&#xff0c;如果键不存在会导致【KeyError】&#xff0c;因此可以考虑用DefaultDict # Defining the dict d defaultdict(def_value) d["a"] 1 d["b"] 2print(d["a"]) print(d["b"]) print(d["c"…...

Redis 底层对 String 的 3 个优化

Redis对 String 类型实现了很多优化&#xff0c;通过以下三个重要的优化点来解释&#xff1a; 1. 简单动态字符串&#xff08;SDS&#xff09; Redis 的 String 类型内部采用简单动态字符串&#xff08;SDS&#xff09;来管理字符串。相比于 C 语言的原生字符串&#xff0c;S…...

简约艺术签名小程序源码/流量主小程序源码/字节跳动抖音小程序

源码简介&#xff1a; 本源码为简约艺术签名小程序、流量主小程序以及字节跳动抖音小程序的源代码。该小程序是一款实用的工具&#xff0c;旨在帮助用户创建各种独特的艺术签名&#xff0c;以便在社交媒体平台上更好地展示用户的个性和创意。 源码链接&#xff1a; 网盘源码 …...

Ubuntu(kylin)挂载iso文件和配置apt本地源

版本说明:Ubuntu Server 16.04 LTS解决问题:解决在无任何互联网的环境下,安装软件时缺少依赖包的问题 方法一:通过虚拟机挂载 将镜像挂载到虚拟机以VMware Workstation为例,打开“虚拟机设置”,点击“CD/DVD”选项,将 “设备状态”中的“<...

wps表格求标准差怎么算?

在WPS表格中&#xff0c;要计算标准差&#xff0c;可以使用STDEV函数。标准差是一种衡量数据集合离散程度的统计指标。下面我将详细介绍如何使用STDEV函数来计算标准差。 STDEV函数的语法为&#xff1a;STDEV(range) 其中&#xff0c;range表示要计算标准差的数据范围&#x…...

安达发|制造企业生产排产现状和APS系统的解决方案

随着市场竞争的加剧&#xff0c;制造业企业面临着生产效率、成本控制和客户满意度等方面的巟大压力。在这种背景下&#xff0c;生产排产作为制造业的核心环节&#xff0c;对企业的生产经营具有重要意义。本文将针对制造业的生产排产现状进行分析&#xff0c;并提出相应的APS系统…...

Qt判断一个点在多边形内还是外(支持凸边形和凹变形)

这里实现的方法是转载于https://blog.csdn.net/trj14/article/details/43190653和https://blog.csdn.net/WilliamSun0122/article/details/77994526 来实现的&#xff0c;并且按照Qt的规则进行了调整。 以下实现方法有四种&#xff0c;每种方法的具体讲解在转载的博客中有说明&…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...