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

Java手写堆排序(Heap Sort)和案例

Java手写堆排序(Heap Sort)

1. 思维导图

下面是使用Mermaid代码绘制的思维导图,用于解释堆排序算法的实现思路原理:

建立最大堆
交换堆顶和最后一个元素
维护最大堆性质
是否完成排序?
结束

2. 手写堆排序的必要性

堆排序是一种高效的排序算法,它的时间复杂度为O(nlogn),具有以下几个方面的优势:

  • 相对于其他基于比较的排序算法(如快速排序、归并排序),堆排序是一种原地排序算法,不需要额外的辅助空间;
  • 堆排序是稳定的排序算法,不会改变相同元素之间的顺序;
  • 堆排序在最坏情况下仍具有较好的性能,因此在一些对排序稳定性要求较高的场景中,堆排序是一个不错的选择。

3. 市场调研

据市场调研,堆排序在实际应用中广泛使用,特别是在以下场景中:

  • 大规模数据的排序:由于堆排序的时间复杂度较低且具备稳定性,因此在需要对大规模数据进行排序的场景中,堆排序是一种常用的选择;
  • 优先级队列:堆排序的基础是堆这种数据结构,而堆被广泛用于实现优先级队列。优先级队列是一种可以动态地插入和删除元素,并且每次操作都能高效地找到最大(或最小)值的数据结构,而堆正是实现这一特性的关键;
  • 排名统计:堆排序在一些需要对数据进行排名统计的场景中也有应用,例如按照成绩对学生进行排名、按照销售额对商品进行排名等。

4. 实现步骤

堆排序的实现步骤包括以下几个部分:

4.1 建立最大堆

首先,我们需要构建一个最大堆,以便后续的排序操作。建立最大堆的步骤如下:

  1. 从最底层的非叶子节点开始,逐层向上调整,使得每个节点都满足最大堆的性质;
  2. 对于当前节点,比较其与左右子节点的大小,如果存在比当前节点更大的子节点,则交换两者的位置;
  3. 重复上述比较和交换的步骤,直到当前节点满足最大堆的性质或成为叶子节点。

以下是建立最大堆的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 维护最大当交换堆顶和最后一个元素后,我们需要维护最大堆的性质,以保证新的堆顶元素是剩下元素中的最大值。

维护最大堆的步骤如下:

  1. 将交换后的堆顶元素(原数组的最后一个元素)下沉到合适的位置,以满足最大堆的性质;
  2. 每次将当前节点与其子节点进行比较,如果存在比当前节点更大的子节点,则将其与其中较大的子节点进行交换;
  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 排序

在建立最大堆和维护最大堆的基础上,我们可以进行堆排序了。

堆排序的步骤如下:

  1. 通过调用建立最大堆的函数,构建一个最大堆;
  2. 从最后一个元素开始,依次将堆顶元素与当前元素进行交换,并缩小堆的范围以排除已排序的元素;
  3. 重复上述交换和缩小堆范围的操作,直到只剩下一个元素。

以下是堆排序的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手写堆排序&#xff08;Heap Sort&#xff09; 1. 思维导图 下面是使用Mermaid代码绘制的思维导图&#xff0c;用于解释堆排序算法的实现思路原理&#xff1a; #mermaid-svg-cFIgsLSm5LOBm5Gl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size…...

Linux设备驱动模型之字符设备

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

Kafka3.0.0版本——消费者(自动提交 offset)

目录 一、自动提交offset的相关参数二、消费者&#xff08;自动提交 offset&#xff09;代码示例 一、自动提交offset的相关参数 官网文档 参数解释 参数描述enable.auto.commi默认值为 true&#xff0c;消费者会自动周期性地向服务器提交偏移量。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…...

马斯洛的动机与人格、需求层次理论

马斯洛是在研究动机&#xff08;Motivation&#xff09;时&#xff0c;才提出需求层次作为理论基础来支持动机理论的。所谓动机&#xff0c;就是人类的行为到底是由什么驱动&#xff0c;其实是对人类行为的当下原动力&#xff0c;区别于过去、未来或者是有可能起作用的动力。 …...

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 " 的报错&#xff1b; 报错的原因原因是推送的文件太大。 下面给出解决方法 方法一&#xff1a; 修改提交缓存大小为500M&#xff0c;或者更大的数字 git config --global http.po…...

Hive内置函数字典

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

svg 知识点总结

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

开源库源码分析:OkHttp源码分析(二)

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

校园地理信息系统的设计与实现

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

Vulnhub实战-prime1

前言 VulnHub 是一个面向信息安全爱好者和专业人士的虚拟机&#xff08;VM&#xff09;漏洞测试平台。它提供了一系列特制的漏洞测试虚拟机镜像&#xff0c;供用户通过攻击和漏洞利用的练习来提升自己的安全技能。本次&#xff0c;我们本次测试的是prime1。 一、主机发现和端…...

Scala学习笔记

Scala学习笔记 Scala笔记一、学习Scala的目的二、Scala的基本概念2.1 JDK1.8版本的新特性2.2 Scala的运行机制 三、Scala的基本语法3.1 Scala中输出语句、键盘输入、注释语法3.1.1 Scala注释三种&#xff0c;和Java一模一样的3.1.2 Scala键盘输入3.1.3 Scala输出 3.2 Scala变量…...

虹科分享 | 软件供应链攻击如何工作?如何评估软件供应链安全?

说到应用程序和软件&#xff0c;关键词是“更多”。在数字经济需求的推动下&#xff0c;从简化业务运营到创造创新的新收入机会&#xff0c;企业越来越依赖应用程序。云本地应用程序开发更是火上浇油。然而&#xff0c;情况是双向的&#xff1a;这些应用程序通常更复杂&#xf…...

gRpc入门和springboot整合

gRpc入门和springboot整合 一、简介 1、gprc概念 gRpc是有google开源的一个高性能的pc框架&#xff0c;Stubby google内部的rpc,2015年正式开源&#xff0c;云原生时代一个RPC标准。 tips:异构系统&#xff0c;就是不同编程语言的系统。 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中还原设计稿中的阴影

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

Hadoop生态圈中的Flume数据日志采集工具

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

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...