排序算法之堆排序
title: 堆排序
date: 2024-7-23 15:48:25 +0800
categories:
- 排序算法
tags: - 排序
- 算法
- 堆排序
description: 堆排序(Heap Sort)是一种基于堆的排序算法,具有较高的效率和稳定性。
math: true
堆排序
堆排序(Heap Sort)是一种基于堆的排序算法,具有较高的效率和稳定性。堆排序利用堆这种完全二叉树的数据结构进行排序,常用的是大顶堆(最大堆)来实现升序排序。本文将详细介绍堆排序的原理、步骤、示例、复杂度分析及其Java代码实现。
堆排序的原理
- 堆的定义:堆是一种完全二叉树,其中每个节点的值都大于或等于其左右子节点的值,这种堆称为大顶堆;每个节点的值都小于或等于其左右子节点的值,这种堆称为小顶堆。
- 通常堆是通过一维[数组]来实现的。在数组起始位置为0的情形中:
- 父节点i的左子节点在位置 ( 2 i + 1 ) (2i+1) (2i+1);
- 父节点i的右子节点在位置 ( 2 i + 2 ) (2i+2) (2i+2);
- 子节点i的父节点在位置 ( i − 1 ) / 2 (i−1)/2 (i−1)/2;
- 堆排序的基本思想:
- 将待排序的数组构造成一个大顶堆。
- 取出堆顶元素(当前堆中最大值),将其与堆的最后一个元素交换。
- 调整堆结构,使其满足堆的性质,重复上述步骤直到整个数组排序完成。
堆排序的步骤
- 构建初始堆:将无序数组构建成一个大顶堆。
- 交换堆顶元素与末尾元素:将堆顶元素(最大值)与末尾元素交换。
- 调整堆:将剩余元素重新调整为大顶堆。
- 重复步骤2和3,直到所有元素有序。
图示

示例

复杂度分析
-
时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)、非自适应排序:建堆操作使用 O ( n ) O(n) O(n) 时间。从堆中提取最大元素的时间复杂度为 O ( log n ) O(\log n) O(logn) ,共循环 n − 1 n - 1 n−1 轮。
-
空间复杂度为 O ( 1 ) O(1) O(1)、原地排序:几个指针变量使用 O ( 1 ) O(1) O(1) 空间。元素交换和堆化操作都是在原数组上进行的。
-
非稳定排序:在交换堆顶元素和堆底元素时,相等元素的相对位置可能发生变化。
时间复杂度
- 所有时间复杂度: O ( n log n ) O(n \log n) O(nlogn)。
空间复杂度
- 空间复杂度: O ( 1 ) O(1) O(1)
堆排序的代码实现(Java)
public class HeapSort {// 主排序函数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 main(String[] args) {int[] arr = {38, 27, 43, 3, 9, 82, 10};System.out.println("Given Array:");for (int num : arr) {System.out.print(num + " ");}System.out.println();// 调用堆排序函数heapSort(arr);System.out.println("\nSorted Array:");for (int num : arr) {System.out.print(num + " ");}System.out.println();}
}相关文章:
排序算法之堆排序
title: 堆排序 date: 2024-7-23 15:48:25 0800 categories: 排序算法 tags:排序算法堆排序 description: 堆排序(Heap Sort)是一种基于堆的排序算法,具有较高的效率和稳定性。 math: true 堆排序 堆排序(Heap Sort)是…...
Python中的NLP宝库:探索顶级库与工具
标题:Python中的NLP宝库:探索顶级库与工具 Python,作为人工智能和机器学习任务中的关键编程语言,为自然语言处理(NLP)提供了丰富的库和工具。这些库不仅功能强大,而且大多数都是开源的…...
springboot + springcloud + Google pubsub+ firebase
1.pom依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-gcp-starter</artifactId><version>1.2.6.RELEASE</version></dependency><dependency><groupId>org.springframe…...
时序数据库TDengine和QuestDB对比
QuestDB和TDengine都是高性能的时序数据库(Time Series Database, TSDB),但它们在设计、功能、适用场景以及性能表现上各有特色。 以下是对两者的详细对比: 一、设计与架构 QuestDB 是一个开源的高性能SQL时序数据库࿰…...
Neuralink的进展与马斯克的技术愿景——从脑机接口到AI融合的未来
引言 Neuralink,这个由埃隆马斯克(Elon Musk)创立的公司,一直是科技界的焦点。自从其发布以来,Neuralink的脑机接口技术便吸引了全球的目光。最近,马斯克再次向公众展示了Neuralink的突破性进展࿰…...
大数据技术——实战项目:广告数仓(第四部分)
目录 第7章 数据仓库环境准备 7.1 数据仓库运行环境 7.1.1 Hive环境搭建 7.1.2 Yarn环境配置 7.2 数据仓库开发环境 第8章 广告数仓ODS层 8.1 广告信息表 8.2 推广平台表 8.3 产品表 8.4 广告投放表 8.5 日志服务器列表 8.6 广告监测日志表 8.7 数据装载脚本 第7章…...
cmake+ninja交叉编译android下的静态库
文章目录 cmakeninja案例背景重新安装ninja编译通过 参考 想整理一个库的cmake工程,他用 cmakeninja 简单了解了一下,是可以不依赖Android studio编译的cmake的,搜到了一个cmakeninja,参考[1] 案例 参考[1]中的代码 背景 cm…...
Vue项目-Table添加Form表单校验
一、HTML <template><div class"taskInfo"><el-form:model"generateParams":rules"formRules"ref"formRef"class"taskInfoForm"label-width"100px"><ul class"taskInfoSearch"&g…...
【iOS】—— 事件传递链和响应者链总结
事件传递链和响应者链总结 1. 事件传递链:事件传递链:传递流程:总结第一响应者: 2. 响应者链响应者链传递流程总结响应者链流程 总结: 之前也学习过这个内容这次在复习的时候,就想着写一下总结:…...
【多线程】初识进程和线程
💐个人主页:初晴~ 📚相关专栏:多线程 / javaEE初阶 前言 在我们之前编写的所有代码,都只能用上一个核心。众所周知,现在大多数CPU都有多个核心,但此时,无论如法优化程序,…...
1DCNN-2DResNet并行故障诊断模型
往期精彩内容: Python-凯斯西储大学(CWRU)轴承数据解读与分类处理 Python轴承故障诊断入门教学-CSDN博客 Python轴承故障诊断 (13)基于故障信号特征提取的超强机器学习识别模型-CSDN博客 Python轴承故障诊断 (14)高创新故障识别模型-CSDN…...
Java设计模式(原型模式)
定义 使用原型实例指定待创建对象的类型,并且通过复制这个原型来创建新的对象。 角色 Prototype(抽象原型角色) ConcretePrototype(具体原型角色) Client(客户端角色 优点 简化对象的创建过程,…...
C/C++ 知识点:typedef 关键字
文章目录 一、typedef 关键字1、 基本用法2、常见用法2.1、为基本数据类型定义别名2.2、为结构体或联合体定义别名2.3、为指针类型定义别名2.4、为复杂模板类型定义别名 3、注意事项4、总结 前言: 在C(以及C语言)中,typedef 关键字…...
【Linux学习】进程间通信之 匿名管道 与 基于管道的进程池
🍑个人主页:Jupiter. 🚀 所属专栏:Linux从入门到进阶 欢迎大家点赞收藏评论😊 目录 🍑进程间通信🐬进程间通信目的 📚管道 📕管道的原理🐧用fork来共享管道原…...
小团队如何选需求管理软件?8款顶级推荐
本文将分享8款适合小团队的需求管理软件:PingCode、Worktile、Tapd、Teambition、禅道、Asana、Jama Connect、Aha!。 在小团队中管理需求时,寻找合适的软件工具常常让人头疼,不同的需求管理软件提供各种功能,但哪些功能真正适合…...
docker操作入门
1.创建镜像,使用当前文件 docker build -t experience . 2.运行容器 docker run -d -p 8501:8501 --name my-running-app my-python-api docker run -p 8508:8508 experience docker run -p 8508:8508 -p 8509:8509 experience 3.查看容器状态 docker ps docker p…...
简单的射箭小游戏网页源码
简单的射箭小游戏网页源码,对准靶心开启你的射击之旅吧 微信扫码免费获取源码...
Python | Leetcode Python题解之第331题验证二叉树的前序序列化
题目: 题解: class Solution:def isValidSerialization(self, preorder: str) -> bool:pre 1for i in preorder.split(,):if i.isdigit():if pre 0:return Falsepre 1else:if pre 0:return Falsepre - 1return pre 0...
0x3 “护网行动”守之道
一、护网防守目标系统 二、护网防守之利器 通过安全流程控制、安全技术保障、安全工具支撑、安全能力提升四个层次全面构成安全防御体系。 安全技术名称解释 IPS(入侵防御系统)WAF(Web应用防火墙)IDS(入侵检测系统&a…...
白骑士的Matlab教学高级篇 3.1 高级编程技术
系列目录 上一篇:白骑士的Matlab教学进阶篇 2.5 Simulink 高级编程技术在MATLAB中扮演着至关重要的角色,帮助用户更高效地编写复杂程序、提高代码的可维护性和可读性。本节将介绍面向对象编程、函数句柄与回调函数、错误处理与调试的相关内容。 面向对…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
