排序算法之堆排序
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中扮演着至关重要的角色,帮助用户更高效地编写复杂程序、提高代码的可维护性和可读性。本节将介绍面向对象编程、函数句柄与回调函数、错误处理与调试的相关内容。 面向对…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
