Java手写堆排序(Heap Sort)和案例
Java手写堆排序(Heap Sort)
1. 思维导图
下面是使用Mermaid代码绘制的思维导图,用于解释堆排序算法的实现思路原理:
2. 手写堆排序的必要性
堆排序是一种高效的排序算法,它的时间复杂度为O(nlogn),具有以下几个方面的优势:
- 相对于其他基于比较的排序算法(如快速排序、归并排序),堆排序是一种原地排序算法,不需要额外的辅助空间;
- 堆排序是稳定的排序算法,不会改变相同元素之间的顺序;
- 堆排序在最坏情况下仍具有较好的性能,因此在一些对排序稳定性要求较高的场景中,堆排序是一个不错的选择。
3. 市场调研
据市场调研,堆排序在实际应用中广泛使用,特别是在以下场景中:
- 大规模数据的排序:由于堆排序的时间复杂度较低且具备稳定性,因此在需要对大规模数据进行排序的场景中,堆排序是一种常用的选择;
- 优先级队列:堆排序的基础是堆这种数据结构,而堆被广泛用于实现优先级队列。优先级队列是一种可以动态地插入和删除元素,并且每次操作都能高效地找到最大(或最小)值的数据结构,而堆正是实现这一特性的关键;
- 排名统计:堆排序在一些需要对数据进行排名统计的场景中也有应用,例如按照成绩对学生进行排名、按照销售额对商品进行排名等。
4. 实现步骤
堆排序的实现步骤包括以下几个部分:
4.1 建立最大堆
首先,我们需要构建一个最大堆,以便后续的排序操作。建立最大堆的步骤如下:
- 从最底层的非叶子节点开始,逐层向上调整,使得每个节点都满足最大堆的性质;
- 对于当前节点,比较其与左右子节点的大小,如果存在比当前节点更大的子节点,则交换两者的位置;
- 重复上述比较和交换的步骤,直到当前节点满足最大堆的性质或成为叶子节点。
以下是建立最大堆的Java代码:
// 建立最大堆
public static void buildMaxHeap(int[] array, int length) {for (int i = length / 2 - 1; i >= 0; i--) {heapify(array, length, i);}
}
4.2 交换堆顶和最后一个元素
建立最大堆之后,最大堆的堆顶元素即为数组中的最大值。我们将堆顶元素与数组中的最后一个元素进行交换。
以下是交换堆顶和最后一个元素的Java代码:
// 交换堆顶和最后一个元素
public static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;
}
4.3 维护最大当交换堆顶和最后一个元素后,我们需要维护最大堆的性质,以保证新的堆顶元素是剩下元素中的最大值。
维护最大堆的步骤如下:
- 将交换后的堆顶元素(原数组的最后一个元素)下沉到合适的位置,以满足最大堆的性质;
- 每次将当前节点与其子节点进行比较,如果存在比当前节点更大的子节点,则将其与其中较大的子节点进行交换;
- 重复上述比较和交换的步骤,直到当前节点满足最大堆的性质或成为叶子节点。
以下是维护最大堆的Java代码:
// 维护最大堆性质
public static void heapify(int[] array, int length, int i) {int largest = i; // 当前节点int left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点比当前节点大if (left < length && array[left] > array[largest]) {largest = left;}// 如果右子节点比当前节点大if (right < length && array[right] > array[largest]) {largest = right;}// 如果最大值不是当前节点,交换它们的位置并继续调整if (largest != i) {swap(array, i, largest);heapify(array, length, largest);}
}
4.4 排序
在建立最大堆和维护最大堆的基础上,我们可以进行堆排序了。
堆排序的步骤如下:
- 通过调用建立最大堆的函数,构建一个最大堆;
- 从最后一个元素开始,依次将堆顶元素与当前元素进行交换,并缩小堆的范围以排除已排序的元素;
- 重复上述交换和缩小堆范围的操作,直到只剩下一个元素。
以下是堆排序的Java代码:
// 堆排序
public static void heapSort(int[] array) {int length = array.length;// 建立最大堆buildMaxHeap(array, length);// 从最后一个元素开始,依次交换堆顶和当前元素,并调整堆for (int i = length - 1; i >= 0; i--) {swap(array, 0, i);heapify(array, i, 0);}
}
5. 手写总结
堆排序是一种高效稳定的排序算法,适用于大规模数据的排序和优先级队列的实现。它的实现步骤包括建立最大堆、交换堆顶和最后一个元素、维护最大堆性质以及排序操作。通过合理地利用最大堆的性质,堆排序能够在O(nlogn)的时间复杂度下完成排序任务。
6. 拓展案例代码
按照成绩对学生进行排名
假设有一个学生列表,每个学生包含姓名和成绩两个属性。我们可以使用堆排序按照成绩对学生进行排名。
class Student {String name;int score;// 构造函数和其他方法省略...
}public static void heapSortByScore(Student[] students) {int length = students.length;// 建立最大堆,按照成绩进行比较buildMaxHeapByScore(students, length);// 从最后一个学生开始,依次交换堆顶和当前学生,并调整堆for (```java
int i = length - 1; i >= 0; i--) {swap(students, 0, i);heapifyByScore(students, i, 0);}
}// 建立最大堆,按照成绩进行比较
public static void buildMaxHeapByScore(Student[] students, int length) {for (int i = length / 2 - 1; i >= 0; i--) {heapifyByScore(students, length, i);}
}// 维护最大堆性质,按照成绩进行比较
public static void heapifyByScore(Student[] students, int length, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < length && students[left].score > students[largest].score) {largest = left;}if (right < length && students[right].score > students[largest].score) {largest = right;}if (largest != i) {swap(students, i, largest);heapifyByScore(students, length, largest);}
}// 交换两个学生的位置
public static void swap(Student[] students, int i, int j) {Student temp = students[i];students[i] = students[j];students[j] = temp;
}
使用示例:
Student[] students = new Student[5];
students[0] = new Student("Alice", 80);
students[1] = new Student("Bob", 75);
students[2] = new Student("Charlie", 90);
students[3] = new Student("David", 85);
students[4] = new Student("Eve", 70);heapSortByScore(students);for (Student student : students) {System.out.println(student.name + ": " + student.score);
}
输出结果:
Charlie: 90
Alice: 80
David: 85
Bob: 75
Eve: 70
按照成绩从高到低排名的结果就是Charlie、Alice、David、Bob、Eve。
这是一个基于堆排序的简单拓展案例,可以根据具体需求进行进一步的扩展和优化。希望对你有帮助!
相关文章:
Java手写堆排序(Heap Sort)和案例
Java手写堆排序(Heap Sort) 1. 思维导图 下面是使用Mermaid代码绘制的思维导图,用于解释堆排序算法的实现思路原理: #mermaid-svg-cFIgsLSm5LOBm5Gl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size…...

Linux设备驱动模型之字符设备
Linux设备驱动模型之字符设备 前面我们有介绍到Linux的设备树,这一节我们来介绍一下字符设备驱动。字符设备是在IO传输过程中以字符为单位进行传输的设备,而字符设备驱动则是一段可以驱动字符设备驱动的代码,当前Linux中,字符设备…...

Kafka3.0.0版本——消费者(自动提交 offset)
目录 一、自动提交offset的相关参数二、消费者(自动提交 offset)代码示例 一、自动提交offset的相关参数 官网文档 参数解释 参数描述enable.auto.commi默认值为 true,消费者会自动周期性地向服务器提交偏移量。auto.commit.interval.ms如果…...
【业务功能116】微服务-springcloud-springboot-Kubernetes集群-k8s集群-KubeSphere-公共服务 DNS
kubernetes集群公共服务 DNS 一、软件安装 # yum -y install bind二、软件配置 # vim /etc/named.conf # cat -n /etc/named.conf1 //2 // named.conf3 //4 // Provided by Red Hat bind package to configure the ISC BIND named(8) DNS5 // server as a caching only…...

马斯洛的动机与人格、需求层次理论
马斯洛是在研究动机(Motivation)时,才提出需求层次作为理论基础来支持动机理论的。所谓动机,就是人类的行为到底是由什么驱动,其实是对人类行为的当下原动力,区别于过去、未来或者是有可能起作用的动力。 …...
TCP/IP网络传输模型及协议
文章目录 前言一、TCP/IP协议二、协议层报文间的封装与拆封1.发送数据2.接收数据前言 TCP/IP模型由OSI七层模型演变而来: 国际标准化组织 1984年提出了模型标准,简称 OSI(Open Systems Interconnection Model)七层模型: 物理层(Physics) :提供机械、电气、功能和过程特性…...

git 推送出现fatal: The remote end hung up unexpectedly解决方案
在使用git更新或提交项目时候出现 "fatal: The remote end hung up unexpectedly " 的报错; 报错的原因原因是推送的文件太大。 下面给出解决方法 方法一: 修改提交缓存大小为500M,或者更大的数字 git config --global http.po…...

Hive内置函数字典
写在前面:HQL同SQL有很多的类似语法,同学熟悉SQL后一般学习起来非常轻松,写一篇文章列举常用函数,方便查找和学习。 1. 执行模式 1.1 Batch Mode 批处理模式 当使用-e或-f选项运行$ HIVE_HOME / bin / hive时,它将以…...

svg 知识点总结
1. 引用 svg,直接用 img 标签 <img src"帐篷.svg" alt"露营">2. 画 svg 各种图形。 矩形 rect圆角矩形 rect圆圈 circle椭圆 ellipse线段 line折线 polyline多边形 polygon路径 path <svg width"200" height"250&qu…...

开源库源码分析:OkHttp源码分析(二)
开源库源码分析:OkHttp源码分析(二) 导言 上一篇文章中我们已经分析到了OkHttp对于网络请求采取了责任链模式,所谓责任链模式就是有多个对象都有机会处理请求,从而避免请求发送者和接收者之间的紧密耦合关系。这篇文章…...

校园地理信息系统的设计与实现
校园地理信息系统的设计与实现 摘 要 与传统的地图相比较,地理信息系统有着不可比拟的优势,信息量大,切换方便,可扩展性强。本文阐述了研究地理信息系统的背景、目的、方法,介绍了一个实用的、方便可靠的校园地理信息…...

Vulnhub实战-prime1
前言 VulnHub 是一个面向信息安全爱好者和专业人士的虚拟机(VM)漏洞测试平台。它提供了一系列特制的漏洞测试虚拟机镜像,供用户通过攻击和漏洞利用的练习来提升自己的安全技能。本次,我们本次测试的是prime1。 一、主机发现和端…...
Scala学习笔记
Scala学习笔记 Scala笔记一、学习Scala的目的二、Scala的基本概念2.1 JDK1.8版本的新特性2.2 Scala的运行机制 三、Scala的基本语法3.1 Scala中输出语句、键盘输入、注释语法3.1.1 Scala注释三种,和Java一模一样的3.1.2 Scala键盘输入3.1.3 Scala输出 3.2 Scala变量…...

虹科分享 | 软件供应链攻击如何工作?如何评估软件供应链安全?
说到应用程序和软件,关键词是“更多”。在数字经济需求的推动下,从简化业务运营到创造创新的新收入机会,企业越来越依赖应用程序。云本地应用程序开发更是火上浇油。然而,情况是双向的:这些应用程序通常更复杂…...

gRpc入门和springboot整合
gRpc入门和springboot整合 一、简介 1、gprc概念 gRpc是有google开源的一个高性能的pc框架,Stubby google内部的rpc,2015年正式开源,云原生时代一个RPC标准。 tips:异构系统,就是不同编程语言的系统。 2、grpc核心设计思路 grpc核心设计…...
基于FPGA点阵显示屏设计-毕设
本设计是一1616点阵LED电子显示屏的设计。整机以EP2C5T144C8N为主控芯片,介绍了以它为控制系统的LED点阵电子显示屏的动态设计和开发过程。通过该芯片控制一个行驱动器74HC154和两个列驱动器74HC595来驱动显示屏显示。该电子显示屏可以显示各种文字或单色图像,采用4块8 x 8点…...
Rocky9.2基于http方式搭建局域网yum源
当前负责的项目有几十台Linux服务器,在安装各类软件的时候需要大量依赖包,而项目部署的环境属于内网环境,与Internet网完全隔离,无法采用配置网络yum源的方式安装rpm包,直接在每台linux服务器上配置本地yum源也比较麻烦,而采用直接下载rpm包用rpm命令安装更是费时费力。所…...
Android 串口通讯
Serial Port Android 串口通讯 arm64-v8a、armeabi-v7a、x86、x86_64 AAR 名称操作serial.jar下载arm64-v8a下载armeabi-v7a下载x86下载x86_64下载arm-zip下载x86-zip下载 Maven 1.build.grade | setting.grade repositories {...maven { url https://jitpack.io } }2./a…...

论如何在Android中还原设计稿中的阴影
每当设计稿上注明需要添加阴影时,Android上总是显得比较棘手,因为Android的阴影实现方式与Web和iOS有所区别。 一般来说阴影通常格式是有: X: 在X轴的偏移度 Y: 在Y轴偏移度 Blur: 阴影的模糊半径 Color: 阴影的颜色 何为阴影 但是在A…...

Hadoop生态圈中的Flume数据日志采集工具
Hadoop生态圈中的Flume数据日志采集工具 一、数据采集的问题二、数据采集一般使用的技术三、扩展:通过爬虫技术采集第三方网站数据四、Flume日志采集工具概述五、Flume采集数据的时候,核心是编写Flume的采集脚本xxx.conf六、Flume案例实操1、采集一个网络…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...