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

排序算法--堆排序

基本思想

堆排序的基本思想是,将待排序的元素构建成一个最大堆或最小堆。对于最大堆来说,堆顶是整个堆中的最大元素;对于最小堆来说,堆顶是整个堆中的最小元素。然后,将堆顶元素与堆中最后一个元素交换,并从堆中移除这个最大或最小元素,再调整剩余的堆,使其满足堆的性质。这个过程重复进行,直到堆中只剩下一个元素,此时数组就被排序了。

算法步骤

  1. 构建最大堆:将待排序的数组从最后一个非叶子节点开始不断向前使用向下调整,使之成为一个最大堆。
  2. 交换堆顶元素与堆尾元素:将堆顶元素(最大值)与堆中最后一个元素交换,此时最后一个元素即为最大值,放置在数组的正确位置。
  3. 调整堆:交换后的堆可能不满足最大堆的性质,因此需要从堆顶开始重新调整堆。
  4. 重复步骤2和3:重复上述过程,每次都会将最大的元素放置在数组的正确位置,直至数组完全有序。

示例代码(从小到大)

建堆有向上调整建堆和向下调整建堆两种,使用向上调整建堆的时间复杂度为O(nlogn),而向下调整建堆的时间复杂度为O(n),所以我们选择向下调整建堆(向下调整详细请看我发布的堆博客)

向下调整
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void AdjustDown(HPDataType* a, int n, int parent)//n为a数组元素个数
{int child = (parent * 2) + 1; // 左子节点位置(假设法找大孩子)while (child < n) // 如果有左子节点,进行循环{if (a[child] < a[child + 1] && child + 1 < n) // 如果右子节点比左子节点大且右子节点存在child++; // 右子节点作为比较对象(大孩子)if (a[child] > a[parent]) // 如果子节点比父节点大{Swap(&a[child], &a[parent]); // 交换子节点和父节点的值parent = child; // 更新父节点位置child = (parent * 2) + 1; // 更新子节点位置}else{break; // 如果子节点比父节点小,则跳出循环}}
}
建大堆并排序
// 堆排序
void HeapSort(int* a, int n)//n为a数组元素个数
{// 建大堆for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(a, n, i); // 向下调整堆}// 排序for (int i = n - 1; i > 0; i--){Swap(&a[i], &a[0]); // 交换堆顶元素和最后一个元素,则最后一个元素为最大的元素AdjustDown(a, i, 0); // 向下调整堆,让堆顶变为最大数}
}

时间复杂度

堆排序的时间复杂度是O(nlogn)。构建最大堆的时间复杂度是O(n),每次调整堆的时间复杂度是O(logn),由于需要调整n-1次,所以总的时间复杂度为O(nlogn)。

空间复杂度

堆排序的空间复杂度是O(1)。它是在原地进行排序的,不需要额外的存储空间。

优点

  • 性能稳定:堆排序的时间复杂度在最好、最坏和平均情况下都是O(nlogn),因此性能稳定。
  • 空间效率高:由于是原地排序算法,不需要额外的内存空间。

缺点

  • 实现复杂:相对于冒泡排序、插入排序等简单排序算法,堆排序的实现相对复杂。
  • 不稳定性:堆排序不是一个稳定的排序算法,相等的元素可能在排序过程中改变它们的相对顺序。

总结来说,堆排序是一种高效、稳定的排序算法,适用于大规模数据的排序,尽管它的实现较为复杂。在实际应用中,堆排序常用于需要性能稳定且空间复杂度低的场景。

相关文章:

排序算法--堆排序

基本思想 堆排序的基本思想是&#xff0c;将待排序的元素构建成一个最大堆或最小堆。对于最大堆来说&#xff0c;堆顶是整个堆中的最大元素&#xff1b;对于最小堆来说&#xff0c;堆顶是整个堆中的最小元素。然后&#xff0c;将堆顶元素与堆中最后一个元素交换&#xff0c;并…...

iPhone 在 App Store 中推出的 PC 模拟器 UTM SE

PC 模拟器是什么&#xff1f;PC 模拟器是一种软件工具&#xff0c;它模拟不同硬件或操作系统环境&#xff0c;使得用户可以在一台 PC 上运行其他平台的应用程序或操作系统。通过 PC 模拟器&#xff0c;用户可以在 Windows 电脑上体验 Android 应用、在 Mac 电脑上运行 Windows …...

FastAPI删除mongodb重复数据(数据清洗)

在 FastAPI 中删除 MongoDB 重复数据&#xff0c;你需要结合使用 MongoDB 查询和 FastAPI 的路由功能。以下是一个通用的例子&#xff0c;演示如何删除特定字段上的重复数据&#xff1a; 1. 定义数据模型: from pydantic import BaseModel, Field from bson import ObjectId …...

移动UI:排行榜单页面如何设计,从这五点入手,附示例。

移动UI的排行榜单页面设计需要考虑以下几个方面&#xff1a; 1. 页面布局&#xff1a; 排行榜单页面的布局应该清晰明了&#xff0c;可以采用列表的形式展示排行榜内容&#xff0c;同时考虑到移动设备的屏幕大小&#xff0c;应该设计合理的滚动和分页机制&#xff0c;确保用户…...

如何解决 uni-app 项目中 “文件查找失败:‘crypto-js‘“ 的问题

在开发使用 uni-app 框架的项目时&#xff0c;遇到依赖问题是常见的。本文将介绍如何解决编译过程中出现的 “文件查找失败&#xff1a;‘crypto-js’” 错误&#xff0c;并说明这种错误为什么会发生以及如何避免。 问题背景 在对 uni-app 项目进行编译时&#xff0c;我们可能…...

Apache DolphinScheduler 3.2.2 版本正式发布!

Apache DolphinScheduler 3.2.2 版本正式发布&#xff01; 近日&#xff0c;Apache DolphinScheduler 发布了 3.2.2 版本。此版本主要基于 3.2.1 版本进行了 bug 修复&#xff0c;新增若干特性&#xff0c;并进行了众多改进和 Bug 修复&#xff0c;以及文档修复等。 &#x1…...

汇川CodeSysPLC教程03-2-6 ModBus TCP

什么是ModBus TCP&#xff1f; ModBus TCP是一种基于TCP/IP协议的工业网络通信协议&#xff0c;常用于工业自动化和控制系统。它是ModBus协议的一个变种&#xff0c;ModBus协议最初由Modicon&#xff08;现在是施耐德电气的一部分&#xff09;在1979年开发。 以下是ModBus TC…...

【Python机器学习】决策树的构造——划分数据集

分类算法除了需要测量信息熵&#xff0c;还需要划分数据集&#xff0c;度量划分数据集的熵&#xff0c;以便判断当前是否正确划分了数据集。 我们将对每个特征划分数据集的结果计算一次信息熵&#xff0c;然后判断按照哪个特征划分数据集是最好的划分方式。 想象一个分部在二…...

Pip换源使用帮助

PyPI 镜像使用帮助 PyPI 镜像帮助提高包安装的速度&#xff0c;特别是当默认源访问较慢时。镜像每次同步成功后&#xff0c;每隔 5 分钟进行更新&#xff0c;确保镜像内容尽量与官方源保持一致。 pip 临时使用 如果您只想在一次安装中使用镜像&#xff0c;可以使用以下命令&…...

力扣1089复写0

1089. 复写零 - 力扣&#xff08;LeetCode&#xff09; 我们的思路是利用类似双指针的方式去解答&#xff0c;来看下代码 class Solution { public:void duplicateZeros(vector<int>& arr){int cur 0, dest -1, n arr.size();while (cur < n){if (arr[cur])d…...

10 VUE Element

文章目录 VUE1、概述2、快速入门3、Vue 指令4、生命周期5、案例 Elemant1、快速入门2、Element 布局3、常用组件-案例 VUE 1、概述 Vue 是一套前端框架&#xff0c;免除原生JavaScript中的DOM操作&#xff0c;简化书写基于MVVM(Model-View-ViewModel)思想&#xff0c;实现数据…...

独立游戏《星尘异变》UE5 C++程序开发日志8——实现敏感词过滤功能(AC自动机)

在游戏中经常会有需要玩家输入一些内容的功能&#xff0c;例如聊天&#xff0c;命名等&#xff0c;这款游戏只有在存档时辉用到命名功能&#xff0c;所以这个过滤也只是一个实验性的功能&#xff0c;我们将使用AC自动机来实现&#xff0c;这是在我们把“csdn”这个词设置为屏蔽…...

使用 Swagger 在 Golang 中进行 API 文档生成

Swagger 是一款强大的 API 文档生成工具&#xff0c;可以帮助开发者轻松创建、管理和展示 RESTful API 文档。在本文中&#xff0c;我们将介绍如何在 Golang 项目中使用 Swagger 来生成 API 文档。 官网地址 &#xff1a; gin-swagger 前提条件 Golang 开发环境&#xff08;…...

Pip换源实战指南:加速你的Python开发

1. Pip换源的重要性 在使用Python进行软件开发或数据分析时&#xff0c;pip 是Python的包管理工具&#xff0c;用于安装和管理第三方库。然而&#xff0c;由于网络环境的差异&#xff0c;特别是在某些国家&#xff0c;访问默认的PyPI&#xff08;Python Package Index&#xff…...

【数据结构】常用数据结构的介绍:理解与应用

文章目录 前言一、介绍二、使用场景三、总结 前言 在计算机科学中&#xff0c;数据结构是我们组织和存储数据的方式&#xff0c;它可以帮助我们高效地执行各种操作&#xff0c;如搜索、插入和删除。从数组和链表&#xff0c;到树和图&#xff0c;不同的数据结构有着不同的优点…...

【优秀python系统毕设】基于Python flask的气象数据可视化系统设计与实现,有LSTM算法预测气温

第一章 绪论 1.1 研究背景 在当今信息爆炸的时代&#xff0c;气象数据作为重要的环境信息资源&#xff0c;扮演着关键的角色。然而&#xff0c;传统的气象数据呈现方式存在信息量庞大、难以理解的问题&#xff0c;限制了用户对气象信息的深入理解和利用。因此&#xff0c;基…...

【康复学习--LeetCode每日一题】2951. 找出峰值

题目&#xff1a; 给你一个下标从 0 开始的数组 mountain 。你的任务是找出数组 mountain 中的所有 峰值。 以数组形式返回给定数组中 峰值 的下标&#xff0c;顺序不限 。 注意&#xff1a; 峰值 是指一个严格大于其相邻元素的元素。 数组的第一个和最后一个元素 不 是峰值。…...

PYTHON学习笔记(八、字符串及的使用)

目录 1、字符串 1.1、字符串的常用操作 1.2、格式化字符串 1.2.1、占位符格式化字符串 1.2.2、f-string格式化字符串 1.2.3、str.format( )格式化字符串 1.3、数据的验证 1.4、正则表达式 1.5.1元字符 1.5.2限定符 1.5.3其他字符 1.5.4re模块 1、字符串 1.1、字符…...

文件共享功能无法使用提示错误代码0x80004005【笔记】

环境情况&#xff1a; 其他电脑可以正常访问共享端&#xff0c;但有一台电脑访问提示错误代码0x80004005。 处理检查&#xff1a; 搜索里输入“启用或关闭Windows功能”按回车键&#xff0c;在“启用或关闭Windows功能”里将“SMB 1.0/CIFS文件共享支持”勾选后&#xff08;故…...

FTP(File Transfer Protocal,文件传输协议)

文章目录 引言FTP管理工具FTP客户端FTP连接模式控制连接数据连接FTP命令/响应FTP命令FTP响应FTPSSFTP引言 FTP(File Transfer Protocal,文件传输协议)用于建立两台主机间的数据文件传输下载。使用客户/服务器(Client/Server)架构,基于TCP协议,服务端口为21。 FTP链接…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...