【面试题】数据结构:堆排序的排序思想?

堆排序的排序思想?

请添加图片描述
堆排序是一种高效的排序算法,其基本思想是利用堆这种数据结构来实现排序。堆是一种特殊的完全二叉树,通常用数组来表示。堆排序的基本步骤如下:

1. 构建初始堆:

  • 将待排序的数组转换成一个最大堆(或最小堆)。在最大堆中,父节点的值总是大于或等于其子节点的值。转换过程从最后一个非叶子节点开始,向上调整堆,确保堆的性质。

2. 堆排序过程:

  • 将堆顶元素(最大值或最小值)与最后一个元素交换,然后将剩余的元素重新调整为堆。
  • 重复上述过程,每次将堆顶元素与当前未排序部分的最后一个元素交换,并重新调整堆,直到整个数组被排序。

3. 调整堆:

  • 每次交换后,需要调整堆以保持堆的性质。调整过程从交换后的堆顶元素开始,向下调整,确保每个节点都满足堆的性质。

4. 循环结束:

  • 当所有元素都通过堆调整并交换到数组的前部时,排序完成。

具体步骤:

  1. 假设数组长度为n,初始时数组为A[1…n]。
  2. 将数组从后向前转换为最大堆:
  • 从最后一个非叶子节点开始(即A[n/2]),向下调整堆。
  • 每个节点向下调整时,比较其值与其子节点的值,如果当前节点的值小于其子节点的值,则与较大的子节点交换。
  • 重复上述过程,直到堆顶元素满足最大堆的性质。
  1. 将堆顶元素(最大值)与数组的最后一个元素交换,然后重新调整堆。
  2. 重复上述过程,直到堆的大小减少到1。

时间复杂度:

  • 堆排序的时间复杂度为O(n log n),其中n是数组的长度。

空间复杂度:

  • 堆排序是原地排序算法,不需要额外的存储空间,因此空间复杂度为O(1)。

稳定性:

  • 堆排序不是稳定的排序算法,因为相同的元素在排序过程中可能会交换位置。

代码:

// 向下调整算法,使以 parent 为根节点的堆满足大根堆性质
void AdjustDown(int* a, int parent, int n)
{assert(a);int child = parent * 2 + 1;// 确保子节点不超过堆的大小while (child < n){// 找到左右子节点中较大的一个if (child + 1 < n && a[child] < a[child + 1]){++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)
{// 升序排序建大根堆,降序排序建小根堆for (int i = (n - 1) / 2; i >= 0; i--) // 从最后一个非叶子节点开始向下调整{AdjustDown(a, i, n); // 向下调整以 i 为根节点的大根堆}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]); // 将堆顶元素(即最大值)与堆末尾元素交换AdjustDown(a, 0, end); // 对新的堆顶进行向下调整,使其满足大根堆性质--end; // 堆大小减 1,排除已排序好的最大值}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/379443.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VS code配置docker远程连接

一 前置条件 1、本地已安装docker 2、服务端docker已配置Docker配置远程连接 二 VScode安装docker扩展 三 执行docker命令 1、切换到远程docker节点 docker context create remote-docker --docker "hosthttp://192.168.6.9:2375" 2、使用远程节点 docker cont…

Xcode进行真机测试时总是断连,如何解决?

嗨。大家好&#xff0c;我是兰若姐姐。最近我在用真机进行app自动化测试的时候&#xff0c;经常会遇到xcode和手机断连&#xff0c;每次断连之后需要重新连接&#xff0c;每次断开都会出现以下截图的报错 当这种情况出现时&#xff0c;之前执行的用例就相当于白执行了&#xff…

分布式搜索引擎ES-Elasticsearch进阶

1.head与postman基于索引的操作 引入概念&#xff1a; 集群健康&#xff1a; green 所有的主分片和副本分片都正常运行。你的集群是100%可用 yellow 所有的主分片都正常运行&#xff0c;但不是所有的副本分片都正常运行。 red 有主分片没能正常运行。 查询es集群健康状态&…

双向链表专题

目录 1. 双向链表的结构 2. 双向链表的实现 2.1 双向链表的初始化 2.2 双向链表的打印 2.3 双向链表的尾插 2.4 双向链表的头插 2.5 双向链表的判空函数 2.6 双向链表的尾删 2.7 双向链表的头删 2.8 双向链表的查找 2.9 在pos位置之后插入节点 2.10 删除指定位置…

云备份服务端

文件使用工具和json序列化反序列化工具 //文件和json工具类的设计实现 #ifndef __UTIL__ #define __UTIL__ #include<iostream> #include<fstream> #include<string> #include <vector> #include<sys/stat.h> #include"bundle.h" #inc…

【C++ | 抽象类】纯虚函数 和 抽象基类,为什么需要抽象基类

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

ETL数据集成丨通过ETLCloud工具,将Oracle数据实时同步至Doris中

ETLCloud是一个全面的数据集成平台&#xff0c;专注于解决大数据量和高合规要求环境下的数据集成需求。采用先进的技术架构&#xff0c;如微服务和全Web可视化的集成设计&#xff0c;为用户提供了一站式的数据处理解决方案。 主要特点和功能包括&#xff1a; 实时数据处理&…

拖拽上传(预览图片)

需求 点击上传图片&#xff0c;或直接拖拽图片到红色方框里面也可上传图片&#xff0c;上传后预览图片 效果 实现 <!DOCTYPE html> <html lang"zh-cn"><head><meta charset"UTF-8"><meta name"viewport" content&…

【QT】label中添加QImage图片并旋转(水平翻转、垂直翻转、顺时针旋转、逆时针旋转)

目录 0.简介 1.详细代码及解释 1&#xff09;原label显示在界面上 2&#xff09;水平翻转 3&#xff09;垂直翻转 4&#xff09;顺时针旋转45度 5&#xff09;逆时针旋转 0.简介 环境&#xff1a;windows11 QtCreator 背景&#xff1a;demo&#xff0c;父类为QWidget&a…

收银系统源码-商城下单,门店接单

随着新零售时代的不断进步&#xff0c;线下线上一体化的收银系统&#xff0c;被很多门店越来越重视。用户在线上商城下单后&#xff0c;门店如何接单呢&#xff0c;如何处理订单呢&#xff1f; 1.收银系统开发语言 核心开发语言: PHP、HTML5、Dart后台接口: PHP7.3后合管理网…

ClickHouse 入门(二)【基础SQL操作】

1、ClickHouse 1.1、SQL 操作 这里只介绍一些和我们之前 MySQL 不同的语法&#xff1b; 1.1.1、Update 和 Delete ClickHouse 提供了 Delete 和 Update 的能力&#xff0c;这类操作被称为 Mutation 查询&#xff08;可变查询&#xff09;&#xff0c;它可以看 做 Alter 的一…

C语言 | Leetcode C语言题解之第241题为运算表达式设计优先级

题目&#xff1a; 题解&#xff1a; #define ADDITION -1 #define SUBTRACTION -2 #define MULTIPLICATION -3int* diffWaysToCompute(char * expression, int* returnSize) {int len strlen(expression);int *ops (int *)malloc(sizeof(int) * len);int opsSize 0;for (in…

钡铼分布式 IO 系统 OPC UA边缘计算耦合器BL205

深圳钡铼技术推出的BL205耦合器支持OPC UA Server功能&#xff0c;以服务器形式对外提供数据。符合IEC 62541工业自动化统一架构通讯标准&#xff0c;数据可以选择加密&#xff08;X.509证书&#xff09;、身份验证方式传送。 安全策略支持basic128rsa15、basic256、basic256s…

Web开发:ASP.NET CORE前后端交互之AJAX(含基础Demo)

目录 一、后端 二、前端 三、代码位置 四、实现效果 五、关键的点 1.后端传输给前端&#xff1a; 2.前端传输给后端 一、后端 using Microsoft.AspNetCore.Mvc; using Microsoft.AspNetCore.Mvc.RazorPages; using Microsoft.AspNetCore.Mvc.Rendering; using WebAppl…

LNMP环境配置问题整理

首先是一键安装直接报错: 换教程:搭建LNMP,步骤最详细,附源码,学不会打我-CSDN博客 mysql安装成功之后: MySQL 启动报错:Job for mysqld.service failed because the control process exited with error code. 如果所有方法都试过之后卸载后重装可以快速解决: 参考…

AI算不出9.11和9.9哪个大?六家大模型厂商总结了这些原因

大模型“答对”或“答错”其实是个概率问题。关于“9.11和9.9哪个大”&#xff0c;这样一道小学生难度的数学题难倒了一众海内外AI大模型。7月17日&#xff0c;第一财经报道了国内外“12个大模型8个都会答错”这道题的现象&#xff0c;大模型的数学能力引发讨论。 “从技术人员…

idea双击没有反应,打不开

问题描述 Error opening zip file or JAR manifest missing : /home/IntelliJ-IDEA/bin/jetbrains-agent.jar解决方案

第三篇 Vue项目目录结构介绍

1、最外层目录结构 passagerFrontPage ├── .vscode //vscode配置&#xff0c;不用理会 ├── node_modules //项目依赖&#xff0c;npm install命令执行后自动生成 ├── public //公共资源存放 ├── src //源码 ├── tests //选装&#xff1a;测试模块 ├── .git…

STM32智能安防系统教程

目录 引言环境准备智能安防系统基础代码实现&#xff1a;实现智能安防系统 4.1 数据采集模块 4.2 数据处理与控制模块 4.3 通信与网络系统实现 4.4 用户界面与数据可视化应用场景&#xff1a;家庭与企业安防管理问题解决方案与优化收尾与总结 1. 引言 智能安防系统通过STM32…

逻辑门的题目怎么做?

FPGA语法练习——二输入逻辑门&#xff0c;一起来听~~ FPGA语法练习——二输入逻辑门 题目介绍&#xff1a;F学社-全球FPGA技术提升平台 (zzfpga.com)