当前位置: 首页 > 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链接…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...

CMS内容管理系统的设计与实现:多站点模式的实现

在一套内容管理系统中&#xff0c;其实有很多站点&#xff0c;比如企业门户网站&#xff0c;产品手册&#xff0c;知识帮助手册等&#xff0c;因此会需要多个站点&#xff0c;甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...

【汇编逆向系列】六、函数调用包含多个参数之多个整型-参数压栈顺序,rcx,rdx,r8,r9寄存器

从本章节开始&#xff0c;进入到函数有多个参数的情况&#xff0c;前面几个章节中介绍了整型和浮点型使用了不同的寄存器在进行函数传参&#xff0c;ECX是整型的第一个参数的寄存器&#xff0c;那么多个参数的情况下函数如何传参&#xff0c;下面展开介绍参数为整型时候的几种情…...