当前位置: 首页 > 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、采集一个网络…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...