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

python 堆排序(Heap Sort)

堆排序(Heap Sort)

堆排序是一种基于二叉堆数据结构的排序算法。它的基本思想是:将待排序的数组构建成一个最大堆(或最小堆),然后依次将堆顶元素(最大值或最小值)与堆的最后一个元素交换,并调整堆,重复这个过程直到整个数组有序。

堆排序的步骤:
  1. 构建最大堆:将数组调整为一个最大堆。
  2. 交换堆顶元素:将堆顶元素(最大值)与堆的最后一个元素交换。
  3. 调整堆:将剩余元素重新调整为最大堆。
  4. 重复过程:重复步骤 2 和 3,直到整个数组有序。
时间复杂度:
  • 最坏情况:O(n log n)
  • 最好情况:O(n log n)
  • 平均情况:O(n log n)
空间复杂度:
  • O(1) —— 堆排序是一种原地排序算法,不需要额外的存储空间。

Python 实现

def heap_sort(arr):n = len(arr)# 构建最大堆for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 逐个提取堆顶元素for i in range(n - 1, 0, -1):arr[i], arr[0] = arr[0], arr[i]  # 交换堆顶元素和最后一个元素heapify(arr, i, 0)  # 调整剩余元素为最大堆return arrdef heapify(arr, n, i):largest = i  # 初始化最大元素为根节点left = 2 * i + 1  # 左子节点right = 2 * i + 2  # 右子节点# 如果左子节点存在且大于根节点if left < n and arr[left] > arr[largest]:largest = left# 如果右子节点存在且大于根节点if right < n and arr[right] > arr[largest]:largest = right# 如果最大元素不是根节点if largest != i:arr[i], arr[largest] = arr[largest], arr[i]  # 交换heapify(arr, n, largest)  # 递归调整子树# 示例使用
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print("排序后的数组:", sorted_arr)

输出结果

排序后的数组: [5, 6, 7, 11, 12, 13]

堆排序的详细过程

以数组 [12, 11, 13, 5, 6, 7] 为例:

  1. 构建最大堆

    • 初始数组:[12, 11, 13, 5, 6, 7]
    • 调整后最大堆:[13, 11, 12, 5, 6, 7]
  2. 交换堆顶元素

    • 将堆顶元素 13 与最后一个元素 7 交换。
    • 数组变为:[7, 11, 12, 5, 6, 13]
  3. 调整堆

    • 调整剩余元素 [7, 11, 12, 5, 6] 为最大堆。
    • 调整后最大堆:[12, 11, 7, 5, 6]
  4. 重复过程

    • 将堆顶元素 12 与最后一个元素 6 交换。
    • 数组变为:[6, 11, 7, 5, 12, 13]
    • 调整剩余元素 [6, 11, 7, 5] 为最大堆。
    • 重复上述步骤,直到整个数组有序。
  5. 最终结果

    • 排序后的数组:[5, 6, 7, 11, 12, 13]

堆排序的优缺点

优点

  • 时间复杂度稳定为 O(n log n),性能优异。
  • 是原地排序算法,不需要额外的存储空间。

缺点

  • 不是稳定的排序算法(相同元素的相对位置可能改变)。
  • 对于小规模数据,性能可能不如插入排序等简单算法。

堆排序的适用场景

  • 需要原地排序的场景。
  • 数据规模较大。
  • 对稳定性没有要求的场景。

总结

堆排序是一种高效的排序算法,适用于大规模数据的排序。通过构建最大堆和逐步提取堆顶元素,可以实现数组的排序。尽管它不是稳定的排序算法,但其时间复杂度和空间复杂度使其在实际应用中具有较高的价值。

相关文章:

python 堆排序(Heap Sort)

堆排序&#xff08;Heap Sort&#xff09; 堆排序是一种基于二叉堆数据结构的排序算法。它的基本思想是&#xff1a;将待排序的数组构建成一个最大堆&#xff08;或最小堆&#xff09;&#xff0c;然后依次将堆顶元素&#xff08;最大值或最小值&#xff09;与堆的最后一个元素…...

word中文献引用[]符号的上下标格式修改

word中文献引用[]符号的上下标格式修改 百度网址 1、查找打开使用通配符&#xff0c;输入[[][0-9]{1,2}[]]&#xff0c;即可匹配所有的字[1],[12]这些字符&#xff0c;然后鼠标点击替换为的空白处&#xff0c;再点击特殊格式–>“字体”&#xff0c;选中上标&#xff0c;最…...

地心地固坐标系

地心地固坐标系&#xff08;ECEF, Earth-Centered, Earth-Fixed&#xff09; 是一种三维坐标系&#xff0c;常用于表示地球表面或地球内部的点的位置。它的特点是坐标系的原点位于地球的质心&#xff0c;并且坐标轴固定在地球表面&#xff0c;并随地球自转而旋转。 ECEF 坐标系…...

3.CSS字体属性

3.1字体系列 CSS使用font-family属性定义文本的字体系列。 p{font-family:"微软雅黑"} div{font-family:Arial,"Microsoft Yahei",微软雅黑} 3.2字体大小 css使用font-size属性定义字体大小 p{ font-size:20px; } px(像素)大小是我们网页的最常用的单…...

使用PyTorch实现的二分类模型示例,综合了CNN、LSTM和Attention技术

以下是一个使用PyTorch实现的二分类模型示例,综合了CNN、LSTM和Attention技术,并尝试满足你提出的各项需求: 1. 数据预处理 扩充输入数据维度 假设你的原始数据是二维的(例如图像或序列数据),可以通过一些变换来扩充维度。例如,对于图像数据,可以进行翻转、旋转、缩放…...

[Wi-Fi]802.11u Vs hotspot2.0

介绍 802.11u 和 Hotspot 2.0 是两个相关但不同的技术标准&#xff0c;它们都旨在改善无线网络的用户体验&#xff0c;特别是在公共 Wi-Fi 环境中。 802.11u 定义&#xff1a;802.11u 是 IEEE 802.11 标准的一个扩展&#xff0c;专注于增强无线网络的互操作性和用户体验。功能…...

VisualStudio 2019 升级遇到的问题及解决

事件起因 今天计划想研究下.net core&#xff08;后面版本直接称为 .net &#xff09;,发现 .net sdk 5.0 最新版本安装不成功。解决之后&#xff0c;真是手欠&#xff0c;看着Visual Studio 2019 有更新了&#xff0c;就直接点击了&#xff0c;这时才发现问题大了。。。 安装…...

Java - 日志体系_Simple Logging Facade for Java (SLF4J)日志门面_SLF4J集成logback 及 原理分析

文章目录 Pre官网集成步骤POM依赖使用第一步&#xff1a;编写 Logback 的配置文件第二步&#xff1a;在代码中使用 SLF4J 原理分析1. 获取对应的 ILoggerFactory2. 根据 ILoggerFactory 获取 Logger 实例3. 日志记录过程 小结 Pre Java - 日志体系_Apache Commons Logging&…...

机器学习-方案设计题(在线医疗诊断项目)

在一个在线医疗诊断项目中&#xff0c;我们希望利用机器学习算法来预测患者是否患有某种疾病。请设计一个方案&#xff0c;包括数据收集、预处理、特征选择、模型选择和评估等步骤来完成这个任务。 1.数据收集数据来源 ‌电子病历系统‌&#xff1a;收集患者的基本信息&…...

基于Sentinel的服务保护方案的三种方式(请求限流、线程隔离、服务熔断)超详细讲解

目录 1、三种方式介绍 1.1请求限流 1.2 线程隔离方案 1.3 服务熔断 2、基于sentinel实现 2.1 启动sentinel 2.2 基于springboot整合sentinel 2.2.1请求限流 2.2.2请求隔离 2.2.2.1 OpenFeign整合Sentinel 2.2.3 服务熔断 2.2.3.1 编写降级代码 2.2.3.2 服务熔断 1、…...

[开源]C++代码分享

一&#xff0c;声明 被人水平有限&#xff0c;开源只是为了分享。勿喷&#xff01;&#xff01;&#xff01;还请大佬指点。 二&#xff0c;代码 // --------------------------------------------------------- 头文件 ----------------------------------------------- #in…...

vulnhub ica1

搭建靶机跟之前一样 不过这个要修改一下网卡;下面链接有教程 vulnhub jangow靶机-CSDN博客 1.扫描靶机IP arp-scan -l 192.168.47.135 2.信息收集 nmap -sS 192.168.47.135 访问网站 这个是一个web应用&#xff0c;框架是qdpm 9.2 在kali上搜索一下发现有两个漏洞&#x…...

Linux(Centos 7.6)基础命令/常用命令说明

1.目录相关命令 命令命令说明pwd用于显示/打印当前目录位置。ls/ll 列出当前目录下的文件或者目录&#xff0c;ll是ls -l的别名&#xff0c;ls仅显示名称&#xff0c;ll会显示详细的目录文件信息。 cd目录切换&#xff0c;常见用法有&#xff0c;cd /切换到根目录&#xff0c;…...

Solon 加入 GitCode:助力国产 Java 应用开发新飞跃

在当今数字化快速发展的时代&#xff0c;Java 应用开发框架不断演进&#xff0c;开发者们始终在寻找更快、更小、更简单的解决方案。近期&#xff0c;Solon 正式加入 GitCode&#xff0c;为广大 Java 开发者带来全新的开发体验&#xff0c;尤其是在国产应用开发进程中&#xff…...

Browser Use:AI智能体自动化操作浏览器的开源工具

Browser Use:AI智能体自动化操作浏览器的开源工具 Browser Use 简介1. 安装所需依赖2. 生成openai密钥3. 编写代码4. 运行代码5. 部署与优化5.1 部署AI代理5.2 优化与扩展总结Browser Use 简介 browser-use是一个Python库,它能够帮助我们将AI代理与浏览器自动化操作结合起来;…...

ArcGIS中怎么进行水文分析?(思路介绍)

最近有人咨询&#xff0c;ArcGIS中怎么进行水文分析&#xff0c;大致的说一下河网提取的思路哈 解决思路&#xff1a;dem填洼→计算水流方向→计算水流累积矩阵→形成河网 dem填洼 计算水流方向 计算水流累积矩阵 用栅格计算器&#xff0c;设阈值&#xff08;自己多次尝试&…...

2024年中国新能源汽车用车发展怎么样 PaperGPT(一)

概述 在国家政策的强力扶持下&#xff0c;2024年中国新能源汽车市场迎来了新的发展机遇。本文将基于《中国新能源汽车用车报告&#xff08;2024年&#xff09;》的数据&#xff0c;对新能源汽车的市场发展和用车趋势概述。 新能源汽车市场发展 政策推动&#xff1a;国家和地…...

KubeOS

title: 探秘 KubeOS&#xff1a;云原生操作系统的创新先锋 date: ‘2024-12-31’ category: blog tags: KubeOS云原生操作系统容器编排 sig: CloudNative archives: ‘2024-12’ author:way_back summary: KubeOS 作为一款专为云原生应用打造的操作系统&#xff0c;深度集成了…...

html文件通过script标签引入外部js文件,但没正确加载的原因

移动端H5应用&#xff0c;html文件通过script标签引入外部js文件&#xff0c;但没正确加载&#xff0c;在移动设备上难以排查。通过PC浏览器打开&#xff0c;发现js被阻止了&#xff1a;blocked:mixed-content。 原因在于&#xff1a; “blocked:mixed - content” 是浏览器的…...

[创业之路-225]:《华为闭环战略管理》-4-华为的商业智慧:在价值链中探索取舍之道与企业边界

目录 一、在价值链中探索取舍之道与企业边界 价值链的深刻洞察 取舍之道&#xff1a;有所为&#xff0c;有所不为 垂直整合与横向整合的平衡 企业边界与活动边界的界定 采购与外包的智慧运用 结语 二、企业外部价值流&#xff1a;上游、中游、下游、终端 上游&#xf…...

让 Agent 具备语音交互能力:技术突破与应用前景(16/30)

让 Agent 具备语音交互能力&#xff1a;技术突破与应用前景 一、引言 在当今数字化时代&#xff0c;人机交互方式正经历着深刻的变革。从早期的命令行界面到图形用户界面&#xff0c;再到如今日益普及的语音交互&#xff0c;人们对于与机器沟通的便捷性和自然性有了更高的追求…...

代理IP助力VR行业革新,小派科技引领技术潮流

随着VR行业的新一轮技术升级&#xff0c;更高分辨率、更宽视场角以及更舒适的佩戴体验已成为各大厂商竞争的核心。在这一浪潮中&#xff0c;小派科技凭借其最新发布的视网膜级VR头显——Crystal Super&#xff0c;成功吸引了市场的目光。而在这场技术革新的背后&#xff0c;代理…...

C#Halcon图像处理畸变校正之曲面校正

图像校正场景一般有两种&#xff0c;其一由镜头本身或安装角度引起&#xff0c;其二是被拍摄物品本身引起 理论处理流程 我的处理处理流程 1&#xff0c;加载网格校正图像 2&#xff0c;确定符合条件的网格区域 3&#xff0c;显示网格鞍点 4&#xff0c;显示网格线 5&#xff…...

JSON结构快捷转XML结构API集成指南

JSON结构快捷转XML结构API集成指南 引言 在当今的软件开发世界中&#xff0c;数据交换格式的选择对于系统的互操作性和效率至关重要。JSON&#xff08;JavaScript Object Notation&#xff09;和XML&#xff08;eXtensible Markup Language&#xff09;是两种广泛使用的数据表…...

Coroutine 基础四 —— CoroutineScope 与 CoroutineContext

1、定位 CoroutineContext&#xff0c;协程上下文。协程用到的所有信息都属于协程上下文&#xff0c;根据功能不同&#xff0c;划分成了不同的分类。管理流程用的是 Job&#xff0c;管理线程用的是 ContinuationInterceptor&#xff0c;等等。 CoroutineScope 的定位有两点&a…...

科技云报到:洞见2025年科技潮流,技术大融合开启“智算时代”

科技云报到原创。 随着2024年逐渐接近尾声&#xff0c;人们不禁开始展望即将到来的2025年。这一年&#xff0c;被众多科技界人士视为开启新纪元的关键节点。站在新的起点上&#xff0c;我们将亲眼目睹未来科技如何改变我们的世界。从人工智能到量子计算&#xff0c;从基因编辑…...

MySQL有哪些锁?

1.MySQL有哪些锁&#xff1f; 全局锁表级锁 表锁元数据锁意向锁 行级锁 记录锁间隙锁临键锁临时意向锁 我了解的是MySQL的锁可以分为全局锁、表级锁、行级锁。 我比较熟悉的是表级锁和行级锁&#xff0c;如果我们对表结构进行修改时&#xff0c;MySQL就会对这个表结构加一个…...

通过交叉实现数据触底分页效果new IntersectionObserver()(html、react、vue2、vue3)中使用

react中用法 import React, { useState, useEffect, useRef } from react;const InfiniteScroll () > {const [items, setItems] useState([]);const [loading, setLoading] useState(false);const [page, setPage] useState(1);const loaderRef useRef(null);// 模拟…...

DeepSeek-V3-Base 模型技术解析

DeepSeek-V3-Base 模型技术解析 目录 引言DeepSeek-V3-Base 模型概述模型架构 3.1 Transformer 基础3.2 DeepSeek-V3-Base 的改进 训练过程 4.1 数据预处理4.2 训练策略4.3 优化器与学习率调度 模型性能评估 5.1 基准测试5.2 实际应用案例 模型优化与调参 6.1 超参数调优6.2 …...

Qt5 中 QGroupBox 标题下沉问题解决

我们设置了QGroupBox 样式之后,发现标题下沉了,那么如何解决呢? QGroupBox {font: 12pt "微软雅黑";color:white;border:1px solid white;border-radius:6px; } 解决后的效果 下面是解决方法: QGroupBox {font: 12pt "微软雅黑";color:white;bo…...

Linux Debian安装ClamAV和命令行扫描病毒方法,以及用Linux Shell编写了一个批量扫描病毒的脚本

ClamAV是一个开源的跨平台病毒扫描引擎&#xff0c;用于检测恶意软件、病毒、木马等安全威胁。 一、Linux Debian安装ClamAV 在Linux Debian系统上安装ClamAV&#xff0c;你可以按照以下步骤进行&#xff1a; 更新软件包列表&#xff1a; 打开终端并更新你的软件包列表&#…...

数据结构与算法之动态规划: LeetCode 53. 最大子数组和 (Ts版)

最大子数组和 https://leetcode.cn/problems/maximum-subarray/description/ 描述 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和子数组是数组中的一个连续部分 示例 1 …...

活动预告 | Microsoft Azure 在线技术公开课:使用 Azure OpenAI 服务构建生成式应用

课程介绍 通过 Microsoft Learn 免费参加 Microsoft Azure 在线技术公开课&#xff0c;掌握创造新机遇所需的技能&#xff0c;加快对 Microsoft Cloud 技术的了解。参加我们举办的“使用 Azure OpenAI 服务构建生成式应用”活动&#xff0c;了解如何使用包括 GPT 在内的强大的…...

Python爬虫(二)- Requests 高级使用教程

文章目录 前言一、Session 对象1. 简介2. 跨请求保持 Cookie3. 设置缺省数据4. 方法级别参数不被跨请求保持5. 会话作为上下文管理器6. 移除字典参数中的值 二、请求与响应1. 请求与响应对象1.1 获取响应头信息1.2 获取发送到服务器的请求头信息 三、SSL 证书验证1. 忽略 SSL 证…...

协议幻变者:DeviceNet转ModbusTCP网关开启机器手臂智能新纪元

技术背景DeviceNet是一种广泛应用于工业自动化领域的现场总线标准&#xff0c;它能够实现控制器与现场设备之间的高效通信&#xff0c;常用于连接各种传感器、执行器以及其他工业设备&#xff0c;如机器人、电机驱动器等&#xff0c;具有实时性强、可靠性高的特点。而ModbusTCP…...

自定义有序Map

package cn.ziqirj.common.utils;import lombok.Getter; import lombok.Setter;import java.util.ArrayList; import java.util.List;/*** 模拟Map集合&#xff0c;key不可重复&#xff0c;按插入顺序排序* author zhangji** param <T>*/ public class CustomOrderlyMap&…...

CA系统的设计(CA证书生成,吊销,数字签名生成)

CA系统概述 CA认证系统是一种基于公钥密码基础设施&#xff08;PKI&#xff09;的信息安全技术&#xff0c;它可以为网络通信双方提供身份认证、数据加密、数字签名等功能。CA认证系统的核心是证书授权机构&#xff08;CA&#xff09;&#xff0c;它负责为用户&#xff08;节点…...

流计算需要框架吗?SPL 可能是更好的选择

流数据源通常是动态、无界的&#xff0c;看起来与静态、有限的批数据源区别较大&#xff0c;传统的数据库技术在架构上难以直接处理流数据源&#xff0c;只能让位于后来者。heron\samza\storm\spark\flink等计算框架最先完成突破&#xff0c;在流计算技术中占得先发优势。这些框…...

Vue-Router之嵌套路由

在路由配置中&#xff0c;配置children import Vue from vue import VueRouter from vue-routerVue.use(VueRouter)const router new VueRouter({mode: history,base: import.meta.env.BASE_URL,routes: [{path: /,redirect: /home},{path: /home,name: home,component: () &…...

MySQL 读写分离

MySQL 读写分离 一、配置主库(Master) 1.修改主库的配置文件 修改主库的 my.cnf 配置文件&#xff0c;生成二进制日志 (binary log) 和服务器唯一ID&#xff0c;这是实现主从复制的必要配置 [mysqld] # skip-grant-tables userroot port3306 basedir/usr/local/mysql datad…...

记一次音频无输出的解决方案

啊啊啊&#xff0c;刷个抖音就发现个死电脑死都不出声&#xff0c;捣鼓了一天才解决 打开wav文件时&#xff0c;提示错误找不到音频播放设备 0xc00d36fa 起初以为是声卡坏了&#xff0c;就到官网下载、更新了声卡驱动。无用什么驱动精灵也检测了&#xff0c;但也测不出啥来。…...

3D数学基础2

矩阵的行列式 在任意方阵中都存在至少一个标量&#xff0c;称作该方阵的行列式。在线性代数中&#xff0c;行列式有很多有用的性质 线性运算法则 方阵 M M M的行列式记作 ∣ M ∣ |M| ∣M∣或“det M”。非方阵矩阵的行列式是未定义的。 注意&#xff0c;在书写行列式时&…...

Java开发生态2024年度总结报告

1 关键要点 尽管数据显示 Java 17 是最常用 JDK&#xff0c;但其用户占比并未超过半数。根据 New Relic 2024 Java 生态系统状态报告&#xff0c;Java 17、11 和 8 的用户比例分别为 35%、33% 和 29%。New Relic 数据中所谓“快速采用”指 Java 21 的采用率仅为 1.4%。虽相较 J…...

1月第三讲:Java子线程无法获取Attributes的解决方法

在Java多线程编程中&#xff0c;开发者经常会遇到子线程无法获取主线程设置的Attributes的问题。Attributes通常用于存储与当前线程相关的数据&#xff0c;尤其在Web应用中&#xff0c;它们常用于请求上下文的管理。然而&#xff0c;由于Java线程是独立运行的&#xff0c;每个线…...

更新金碟云星空单据供应商和币别

--应付单 select FSUPPLIERID from [dbo].[T_AP_PAYABLE] where FBILLNO=AP2024121670 select FSUPPLIERID,FCURRENCYID,* from [dbo].[T_AP_PAYABLE] where FBILLNO=AP2024121670 -- update T_AP_PAYABLE set FSUPPLIERID=100567 where FBILLNO=AP2024121670 -- update T_…...

from memory cache 修复记录

背景 浏览器的页签图标&#xff0c;不想要了 改代码&#xff1a;设置浏览器页签的代码 本地环境测试&#xff0c;没有问题&#xff0c;一次性修改成功 于是打包&#xff0c;部署到测试环境&#xff0c;然而&#xff0c;还是有 接下的解决方法&#xff1a; 1、清除浏览器缓…...

spring入门程序

安装eclipse https://blog.csdn.net/qq_36437991/article/details/131644570 新建maven项目 安装依赖包 pom.xml <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation&quo…...

用于实现无缝滚动效果的vue-seamless-scroll插件

它通常用于在网页或应用中实现内容的自动滚动效果&#xff0c;如新闻公告、图片轮播等&#xff0c;支持横向和纵向滚动&#xff0c;并且可以自定义滚动速度、方向等参数&#xff0c;适合展示一些需要持续循环展示的信息。 在Vue2项目中使用vue-seamless-scroll插件的步骤如下&…...

借助 FinClip 跨端技术探索鸿蒙原生应用开发之旅

在当今数字化浪潮汹涌澎湃的时代&#xff0c;移动应用开发领域正经历着深刻的变革与创新。鸿蒙操作系统的崛起&#xff0c;以其独特的分布式架构和强大的性能表现&#xff0c;吸引了众多开发者的目光。而FinClip 跨端技术的出现&#xff0c;为开发者涉足鸿蒙原生应用开发提供了…...

【机器学习】机器学习的基本分类-自监督学习-对比学习(Contrastive Learning)

对比学习是一种自监督学习方法&#xff0c;其目标是学习数据的表征&#xff08;representation&#xff09;&#xff0c;使得在表征空间中&#xff0c;相似的样本距离更近&#xff0c;不相似的样本距离更远。通过设计对比损失函数&#xff08;Contrastive Loss&#xff09;&…...