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

堆排序简介

概念

堆排序是一种基于二叉堆数据结构的排序算法。它的概念是通过将待排序的元素构建成一个二叉堆,然后通过不断地取出堆顶元素并重新调整堆的结构来实现排序。

算法步骤

  1. 构建最大堆(或最小堆):将待排序的元素构建成一个二叉堆。最大堆的特点是父节点的值大于其子节点的值,最小堆的特点是父节点的值小于其子节点的值。
  2. 交换堆顶元素和最后一个元素:将堆顶元素与堆中最后一个元素交换位置,然后将堆的大小减1。
  3. 调整堆结构:对交换后的堆顶元素进行调整,使其满足堆的性质。
  4. 重复步骤2和步骤3,直到堆的大小为1。

算法特点

  • 堆排序是一种原地排序算法,不需要额外的存储空间。
  • 时间复杂度为O(nlogn),其中n是待排序元素的个数。
  • 不稳定排序算法,可能改变相同值的元素的相对顺序。

优点

  • 相对于其他排序算法,堆排序的常数因子较小,因此在大规模数据的排序中表现较好。
  • 由于堆排序的每一次交换都是跨越较大的距离,因此对于顺序存储的数据,堆排序的缓存命中率较高。

缺点

  • 堆排序的主要缺点是在排序过程中,需要频繁地进行元素的比较和交换,因此相对于其他排序算法,它的性能较差。
  • 不适合对于小规模数据的排序。

适用场景

  • 堆排序适用于大规模数据的排序,尤其是外部排序(数据量无法一次性装入内存)的情况下。
  • 由于堆排序对数据的随机访问较多,因此在数据的存储方式为顺序存储时,堆排序的性能较好。

实现代码

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 temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}}public static void main(String[] args) {int[] arr = { 4, 10, 3, 5, 1, 11, 33, 7, 12, 9 }};heapSort(arr);System.out.println("排序结果:");for (int num : arr) {System.out.print(num + " ");}}
}

相关文章:

堆排序简介

概念&#xff1a; 堆排序是一种基于二叉堆数据结构的排序算法。它的概念是通过将待排序的元素构建成一个二叉堆&#xff0c;然后通过不断地取出堆顶元素并重新调整堆的结构来实现排序。 算法步骤&#xff1a; 构建最大堆&#xff08;或最小堆&#xff09;&#xff1a;将待排…...

React Diff算法

文章目录 React Diff算法一、它的作用是什么&#xff1f;二、React的Diff算法1.了解一下什么是调和&#xff1f;2.react的diff算法3.React Diff的三大策略4.tree diff&#xff1a;1、如果DOM节点出现了跨层级操作&#xff0c;Diff会怎么办? 5. component diff&#xff1a;6. e…...

07 mysql5.6.x docker 启动, 无 config 目录导致客户端连接认证需要 10s

前言 呵呵 最近再一次 环境部署的过程中碰到了这样的一个问题 我基于 docker 启动了一个 mysql 服务, 然后 挂载出了 数据目录 和 配置目录, 没有手动复制配置目录出来, 所以配置目录是空的 然后 我基于 docker 启动了一个 nacos, 配置数据库设置为上面的这个 mysql 然后 启…...

GO GC

GO GC 垃圾回收(Garbage Collection&#xff0c;简称GC)是编程语言中提供的自动的内存管理机制&#xff0c;自动释放不需要的对象&#xff0c;让出存储器资源&#xff0c;无需程序员手动执行。 Golang中的垃圾回收主要应用三色标记法&#xff0c;GC过程和其他用户goroutine可…...

ECharts配合Node.js爬虫实现数据可视化

数据可视化简介 可视化技术是将数据和信息以图形化的方式展示出来&#xff0c;以便更好地理解和分析。可视化技术通常使用各种图表、图形、动画和交互式效果来呈现数据。可视化技术有以下几个基本概念&#xff1a; 数据&#xff1a;可视化技术的基础是数据。数据可以是数字、文…...

[Linux] C获取键盘,鼠标数据

键盘检测指令&#xff1a;cat /dev/input/event1 | hexdump 鼠标检测指令&#xff1a;cat /dev/input/event2 | hexdump 当键盘/鼠标有输入时&#xff0c;会有对应的一堆16进制输出。它其实对应着input_event结构体【24字节】。 struct input_event {struct timeval time;_…...

户外跑步用什么耳机、户外运动耳机推荐

跑步是一项简单的运动&#xff0c;只需要交替迈左右腿就可以进行。然而&#xff0c;跑步有时可能变得单调乏味。即使是意志坚定、热爱跑步的人&#xff0c;在这个漫长的过程中也会感到乏味&#xff0c;更不用说像你我这样的普通跑者了。音乐能够让跑步变得更加有趣&#xff0c;…...

ubuntu设置系统代理

安装trojan等代理工具并配置启动&#xff0c;得到端口号 例如 10.10.1.10:8080系统代理设置 我们将在/etc/profile.d/proxy.sh下添加一个shell脚本文件&#xff0c;这将确保设置适用于所有已登录的用户&#xff1a; sudo vim /etc/profile.d/proxy.sh将以下内容写到文档中&…...

java定时任务如何取消

java定时任务如何取消&#xff0c;并比如&#xff0c;我之前想每周二晚上6点自动生成一条devops流水线&#xff0c;现在我想停掉 答案&#xff1a; 在Java中&#xff0c;可以使用ScheduledExecutorService类来创建定时任务。要取消定时任务&#xff0c;可以调用ScheduledFutur…...

gitlab 9.05 版本获取合并请求的API接口报错404是为什么

gitlab 9.05 版本获取合并请求的API接口报错404是为什么 答案&#xff1a; 出现404错误表示请求的资源未找到。在这种情况下&#xff0c;可能有以下几个原因导致API接口报错404&#xff1a; 版本不匹配&#xff1a;请确保你使用的是GitLab 9.05版本的API接口&#xff0c;如果使…...

微服务(多级缓存)

目录 多级缓存 1.什么是多级缓存 2.JVM进程缓存 2.2.初识Caffeine 2.3.实现JVM进程缓存 2.3.1.需求 2.3.2.实现 3.Lua语法入门 3.1.初识Lua 3.1.HelloWorld 3.2.变量和循环 3.2.1.Lua的数据类型 3.2.2.声明变量 3.2.3.循环 3.3.条件控制、函数 3.3.1.函数 3.3.…...

阿里云配置MySQL-server 8.0远程登录

Ubuntu 22.04 LTS 安装MySQL-Server 8.0 # apt search mysql-server # apt install mysql-server重建服务 # service mysql stop # vi /etc/mysql/mysql.conf.d/mysqld.cnf ... bind-address 0.0.0.0 ... # service mysql start # lsof -i:3306 COMMAND PID USER FD …...

清洁能源使用的社会发展意义

应用清洁能源是转变经济增加途径的有效手段&#xff0c;能够在减少污染物、降低企业经营成本的同时&#xff0c;提高企业经济效益和社会经济效益。 应用清洁能源是保护环境的最佳方式和必然选择&#xff0c;改变末端治理的现状&#xff0c;采取以预防为主的环境保护与发展理…...

针对论坛系统进行功能测试和性能测试

项目链接:飞鸽论坛 目录 一. 项目背景 二. 项目功能 三. 功能测试 注册: 登录: 更改用户信息: 发布帖子: 更新帖子信息: 点赞: 评论: 发送私信: 测试报告 四. 性能测试 Virtual User Generator Controller Analysis 测试报告: 一. 项目背景 该论坛系统采用前…...

Android App的设计规范

Android App 设计规范是为开发者和设计师提供的一系列准则和建议&#xff0c;以确保应用在 Android 设备上的外观、交互和用户体验保持一致。以下是一些常见的 Android App 设计规范要点&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开…...

paddleclas ImportError: cannot import name ‘Identity‘ from ‘paddle.nn‘

使用paddlepaddle的 paddleclas 官方demos时 &#xff0c;报错如图 ImportError: cannot import name ‘Identity’ from ‘paddle.nn’ 解决方案很简单&#xff1a; 找到调用 Identity 的位置&#xff1a; 注释掉就解决啦 !!! 搞定&#xff01;&#xff01;&#xff01;…...

Debezium系列之:深入理解Debezium Server Operator和实际应用Debezium Server Operator案例详解

Debezium系列之:深入理解Debezium Server Operator和实际应用Debezium Server Operator案例详解 一、认识Debezium Server Operator二、深入理解Debezium Server和Debezium Server实际应用案例详解三、Debezium Server Operator安装步骤四、Debezium Operator使用案例五、post…...

ansible批量创建crontab文件并添加到定时任务

Ansible 来修改 crontab 文件并添加计划任务。用于将你提供的 cron 行添加到特定用户的 crontab 中&#xff1a; --- - name: Add cron job to users crontabhosts: your_target_hosttasks:- name: Add cron jobcron:name: "ntpdate_job"minute: "0"hour:…...

什么是 API ?

一、API 的定义&#xff1a;数据共享模式定义 4 大种类 作为互联网从业人员&#xff0c;API 这个词我耳朵都听起茧子了&#xff0c;那么 API 究竟是什么呢&#xff1f; API 即应用程序接口&#xff08;API&#xff1a;Application Program Interface&#xff09;&#xff0c;…...

CSS实现内凹圆角,从而实现圆角边框

1、代码 <!DOCTYPE html> <html><head><style>.uu {position: relative;width: 400px;height: 300px;}img {width: 100%;height: 100%;z-index: 1;}.box_right_top {background-image: radial-gradient(circle at left bottom, transparent 50px, whi…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

大模型真的像人一样“思考”和“理解”吗?​

Yann LeCun 新研究的核心探讨&#xff1a;大语言模型&#xff08;LLM&#xff09;的“理解”和“思考”方式与人类认知的根本差异。 核心问题&#xff1a;大模型真的像人一样“思考”和“理解”吗&#xff1f; 人类的思考方式&#xff1a; 你的大脑是个超级整理师。面对海量信…...

Linux中INADDR_ANY详解

在Linux网络编程中&#xff0c;INADDR_ANY 是一个特殊的IPv4地址常量&#xff08;定义在 <netinet/in.h> 头文件中&#xff09;&#xff0c;用于表示绑定到所有可用网络接口的地址。它是服务器程序中的常见用法&#xff0c;允许套接字监听所有本地IP地址上的连接请求。 关…...

ABB馈线保护 REJ601 BD446NN1XG

配电网基本量程数字继电器 REJ601是一种专用馈线保护继电器&#xff0c;用于保护一次和二次配电网络中的公用事业和工业电力系统。该继电器在一个单元中提供了保护和监控功能的优化组合&#xff0c;具有同类产品中最佳的性能和可用性。 REJ601是一种专用馈线保护继电器&#xf…...