堆排序----C语言数据结构

目录

    • 引言
  • 堆排序的实现
    • **堆的向下调整算法**
  • 对排序的时间复杂度
    • 建堆的时间复杂度:
    • 排序过程的时间复杂度:
    • 总体时间复杂度:

引言

堆排序(Heap Sort)是一种基于比较的排序算法,利用堆的数据结构来实现。它的时间复杂度为O(n log n),并且是原地排序算法,不需要额外的存储空间,这使得它在空间复杂度方面具有优势。

堆排序的关键在于构建和维护堆的性质。虽然堆排序的时间复杂度较好,但在实际应用中,由于其不具备插入和删除操作的优势,因此在一些特殊方面很少被选择。

堆排序的实现

堆排序实现的基本思路为:

  1. 建堆
    升序:建大堆
    降序:建小堆
  2. 利用堆删除思想来进行排序
    建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。
    在这里插入图片描述

堆的向下调整算法

从给出的 一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
如图:
在这里插入图片描述

void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}

void AdjustDwon(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while(child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			//先假设左孩子最小,不成立便改为右孩子
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child ;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

在一个堆中,根节点从0开始编号,下标为 i(i > 0) 的结点的左右孩子结点及父结点的下标:
左孩子:2i(i>0)
右孩子:2i+1
父节点: (i-1)/2
根据树的父子结点的联系来确定数组下标

void HeapSort(int* a, int n)
{
	//起始i用n-1是数组的最后一个为n-1,起始i为最后一个元素的父节点
	for (int i = (n - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDwon(a, n, i);
	}
	int end = n - 1;
	//建好大堆,将最大值交换置数组的最后,然后排出最后一个元素,对前n-1的数组进行建堆
	while(end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}

对排序的时间复杂度

建堆的时间复杂度:

在堆排序中,首先需要将待排序的序列构建成一个最大堆。构建最大堆的时间复杂度是O(n),其中 n 是待排序序列的长度。这是因为我们只需要对具有父子关系的一半节点进行堆化操作,而这一半节点通常是 n/2。

排序过程的时间复杂度:

堆排序的排序过程包括了 n-1 次交换和堆调整的操作。每次交换涉及到堆顶元素与末尾元素的交换,然后对剩余的 n-1 个元素进行堆调整。堆调整的时间复杂度为O(log n)。因此,排序过程的总时间复杂度为 O((n-1) * log n),约等于O(n log n)。

总体时间复杂度:

将建堆和排序过程的时间复杂度结合起来,堆排序的总体时间复杂度为 O(n + n log n)。在大 O 表示法中,通常会忽略掉低阶项和常数系数,因此可以简化为 O(n log n)。

堆排序的时间复杂度是相对较好的,且具有原地排序的特点。然而,需要注意的是,堆排序在实际应用中可能会因为其不具备稳定性(相同元素的相对位置可能发生变化)和对缓存的不友好等原因而被其他算法替代。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【数据结构与算法】力扣刷题记之 稀疏数组

&#x1f389;&#x1f389;欢迎光临&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;特别推荐给大家我的最新专栏《数据结构与算法&#xff1a;初学者入门指南》&#x1f4d8;&am…

LLM应用开发与落地:流式响应

一、背景 最近智能客服产品给到一个游戏客户那边&#xff0c;客户那边的客服负责人体验后认为我们产品回答的准确率是还是比较高的。同时&#xff0c;他反馈了几个需要改进的地方&#xff0c;其中一个就是机器人回复慢。机器人回复慢有很多原因&#xff0c;也有优化方式&#…

接口测试常见问题

1.接口测试的流程 测试计划与方案 --> 接口用例设计 --> 接口测试执行 --> 缺陷报告与结果分析 2.接口工具的流程 脚本的设计&#xff0c;数据用例的设计&#xff0c;断言&#xff08;预期结果的设计&#xff09;&#xff0c;执行 3.测试计划与方案&#xff1a; …

如何手机搜大学生答案? #笔记#微信

今天我就分享几款搜题软件和搜题网站给大家&#xff0c;每一款都能轻松搜索题目&#xff0c;让大家快速找到精准的答案&#xff0c;有需要的小伙伴快点赞收藏起来&#xff0c;防止需要的时候找不到啦。 1.试题猪 这个是公众号 涵盖初大学&#xff0f;专升本&#xff0f;考研…

猫头虎分享已解决Bug || 缓存溢出解决方案:CacheOverflowException 或 CacheOutOfMemoryError

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

自然人如何代开发票

1&#xff1a;登录国家税务总局深圳市电子税务局 地址&#xff1a;国家税务总局深圳市电子税务局 2&#xff1a;个人所得税APP 扫描登录 或 身份证登录 3&#xff1a;选择 自然人代开增值税电子普通发票 4&#xff1a;申请代开 5&#xff1a;人脸识别 6&#xff1a;画框的…

那些 C语言指针 你不知道的小秘密 (4)

本篇会加入个人的所谓‘鱼式疯言’ ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 我会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人能…

C# 字体大小的相关问题

设置字体大小无法这么写&#xff0c; button1.Font.Size 20&#xff1b; 这个是只读属性&#xff1b; 把字体大小改为16&#xff0c; button2.Font new Font(button2.Font.Name, 16); 程序运行的时候先看一下窗体和控件的默认字体尺寸&#xff0c;都是9&#xff1b;然后点b…

【JAVA WEB】盒模型

目录 边框 内边距 基础写法 复合写法 外边距 基础写法 复合写法 块级元素的水平居中 弹性布局 设置行内元素的属性 &#xff0c;span 每一个HTML元素就相当于是一个矩形的“盒子” 这个盒子由以下这几个部分构成&#xff1a; 1.边框 border 2.内容 content 3.内边…

铱塔 (iita) 开源 IoT 物联网开发平台,基于 SpringBoot + TDEngine +Vue3

01 铱塔 (iita) 物联网平台 铱塔智联 (open-iita) 基于Java语言的开源物联网基础开发平台&#xff0c;提供了物联网及相关业务开发的常见基础功能, 能帮助你快速搭建自己的物联网相关业务平台。 铱塔智联平台包含了品类、物模型、消息转换、通讯组件&#xff08;mqtt/EMQX通讯组…

【MyBatis面试题】

目录 前言 1.MyBatis执行流程。 2.Mybatis是否支持延迟加载&#xff1f; 3.延迟加载的底层原理知道吗&#xff1f; 4.Mybatis的一级、二级缓存用过吗&#xff1f; 5.Mybatis的二级缓存什么时候会清理缓存中的数据&#xff1f; 总结 前言 本文主要介绍了MyBatis面试题相…

4.1 Verilog 过程结构

关键词&#xff1a;initial&#xff0c; always 过程结构语句有 2 种&#xff0c;initial 与 always 语句。它们是行为级建模的 2 种基本语句。 一个模块中可以包含多个 initial 和 always 语句&#xff0c;但 2 种语句不能嵌套使用。 这些语句在模块间并行执行&#xff0c;…

基础图算法与社交网络分析

目录 前言1 寻找最短路径的Dijkstra算法1.1 介绍1.2 算法步骤1.3 应用领域1.4 算法优势与限制 2 构建高效网络结构的最小生成树算法2.1 Kruskal算法2.2 应用领域2.3 算法优势与限制 3 中心度算法3.1 PageRank算法3.2 Degree Centrality&#xff08;度中心度&#xff09;3.3 Bet…

上位机图像处理和嵌入式模块部署(利用python开发软件)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 开发windows和linux软件的时候&#xff0c;大家一般都是习惯于用c/c语言进行开发&#xff0c;但是目前来说很多的开发板都是支持python语言开发的。…

【网站项目】032汽车客运站管理系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

数据湖的整体思路

湖本质上是一个集中化&#xff0c;中心化的&#xff0c;一体化的存储技术&#xff0c;并且在其之上追求技术架构的统一化&#xff0c;如流批一体&#xff0c;服务分析一体化。 当数据湖成为中心&#xff0c;那么就可以围湖而建“数据服务环”&#xff0c;环上的服务包括了数仓、…

Python 视频转场特效处理笔记

本文参考Python-OpenCV 实现美图秀秀视频剪辑效果【特效】_opencv 多张图片 视频 特效-CSDN博客 最近研究了点python处理视频相关的东西&#xff0c;本文展示特效包括&#xff0c;竖向开幕/横向开幕&#xff0c;渐隐/渐显&#xff0c;推近/拉远&#xff0c;方形开幕&#xff0…

降准是什么意思?降准对股市有哪些影响?

降准是什么意思 降准&#xff0c;全称为“中央银行调低法定存款准备率”&#xff0c;是指中央银行降低法定存款准备率&#xff0c;以增加银行的可用资金&#xff0c;从而增加市场的流动性。 具体来说&#xff0c;存款准备金是商业银行为了应对储户取款和清算时准备的资金&…

Java集合框架(包装类、泛型)

前言&#xff1a; 本篇文章我们来讲解Java中的集合框架&#xff0c;就相当于车轮子。Java是面向对象的语言&#xff0c;所以相对于C语言有自身优势&#xff0c;就比如现成的数据结构&#xff08;比如栈&#xff0c;队列&#xff0c;堆等&#xff09;。Java的集合框架大家也不用…

猫头虎分享已解决Bug || 响应式布局错误(Responsive Design Issues):在移动设备上元素重叠、布局错位

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …