【排序算法】堆排序(Heapsort)

✨✨✨专栏:排序算法 

          🧑‍🎓个人主页:SWsunlight

目录

​编辑

前言:

一、堆排序:

时间复杂度:

空间复杂度:

算法稳定性:

二、升序的实现:通过建大堆实现

>思路:

1、向上调整算法实现大堆的建立:了解即可

 2、向下调整算法实现大堆的建立:

 3、排序:

 代码实现升序:

三、降序的实现:通过建小堆实现

>思路:

1、向上调整算法实现小堆的建立:了解即可

​编辑

2、向下调整算法实现小堆的建立:

​编辑

3、排序:

代码:

四、建堆的时间复杂度计算:

五、总结:



前言:

        本文基于对堆已经理解并通过代码实现后进行的,不知道堆的可以看上篇文章:堆

一、堆排序:

概念:   堆排序(Heapsort)是指利用 堆 这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆

利用了堆的特点:堆分为大根堆和小根堆,是完全二叉树。为啥升序大堆,降序小堆:大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。相反小堆最小值一定在堆顶;

时间复杂度:

        堆排序包括构建堆排序两个操作:
        构建堆的时间复杂度:              T(n) = O(n)
        排序过程的时间复杂度:         ​​​​  T(n) = O(nlog2n)
        堆排序整体的时间复杂度:       T(n) = O(nlog2n)

空间复杂度:

         O(1)     实现排序不需要额外的空间,就是以数组自身的空间进行的

算法稳定性:

           堆的调整过程中,值相同的结点在比较过程中不能保证顺序,所以堆排序是一种不稳定的排序方法

二、升序的实现:通过建大堆实现

>思路:

  1. 将待排序数组构造成一个大堆
  2. 这个序列最大值在堆顶
  3. 将其与末尾元素进行交换,末尾变成最大值
  4. 将剩下的n-1个结点重新调整为大堆
  5. 再次将最大值与新的末尾元素(此时有n-1个结点)交换
  6. 重复下去,到最后就是有序的了,整个数组最小的元素此时在栈顶

1、向上调整算法实现大堆的建立:了解即可

我们将上图数组的第一个元素作为堆顶(即下标为0的元素),进行建堆,然后将第二个数据看成是插入堆(会进行比较,谁大谁会放到堆顶),依次类推,直到数组的最后一个元素,就是模拟的大堆进行插入操作,只是这些值已经有了,相当于插好了,只是需要进行调整

如下是我们将数组在逻辑结构上画成堆的样子,但不是堆,不满足堆的性质,所以需要我们进行调整算法

看下面:从第二层开始进行调整,根据下标来进行的,依次类推,会一直调整到最后一个元素

 流程图:手绘的 红色箭头表示所在下标(位置) 黑色就是结束一次向上调整函数

堆也就建立如下图:是大堆,但是不是有序的,让他变成有序,等会将考虑,一口吃不成胖子

 向上调整的算法:

下标为0开始的

 2、向下调整算法实现大堆的建立:

堆的删除就是使用的向下调整算法,我们会发现删除的前提是它是,那么若是将数组的首元素直接向下调整是不行的因为此时这个数组逻辑上看它就不是堆,若是左子树、右子树是大堆,那么我就可以直接向下调整;

我们想办法将左右子树变成大堆;是不是可以逆向思维呢?叶子节点是不可以向下调整的,那我找到叶子结点的父节点,是不是就可以进行调整,一点一点从数组的最后一个元素开始,但是看图我们会发现实际是从第一个非子叶结点开始的 上图变左、右子树,最后到了根结点,让根结点向下调整,就完成了大堆的建立

如下图流程:

向下调整的算法: 

叶子结点的父亲开始传,这个不就是通过孩子节点求父亲的公式么;开始传

 3、排序:

简单多了类似堆的删除(假删除并不是真的删除o);是将根结点先与最后一个结点互换,然后将

元素个数n-1  将新的元素个数传上去进行向下调整

 因为堆顶元素在这个堆中用远是最大的,所以不断的将堆顶元素和堆的最后一个元素进行交换,直到将这个大堆变成只剩下根结点的堆,此时数据变成有序了

这个过程我的堆的元素个数在不断减小

 代码实现升序:

typedef int HpDataType;
//交换数据
void Swp(HpDataType* p1, HpDataType* p2)
{
	assert(p1 && p2);
	HpDataType tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}

//大堆:向上调整,child 为孩子
void AdjustUpBig(HpDataType* a, int child)
{
	assert(a);
	//parent 父亲结点
	int  parent = (child - 1) / 2;
	//循环的进行从3个方面考虑:
	// 1、初始条件
	// 2、中间过程
	// 3、结束条件
	//循环有2种写法:
	while (child > 0 && a[child] > a[parent])
	{
		//互换;
		Swp(&a[child], &a[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
	
}
//大堆:向下调整  //数组  元素个数  parent 父亲节点
void AdjustDownBig(HpDataType* a, int n, int parent)
{
	assert(a);
	//用到假设法:我们要保证我的父亲节点比最大的儿子节点大或者相等;假设左孩子大
	int child = 2 * parent + 1;
	while (child < n)
	{//判断一下,完全二叉树,有可能会有有孩子不存在的情况
		if (a[child] < a[child + 1] && child + 1 < n)
		{
			//拿孩子大的去和父亲比较
			child = child + 1;
		}
		if (a[child] > a[parent])
		{
			Swp(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}

	}

}

//打印
void Prin(int* a, int n)
{
	int i;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

//大堆:变量含义:数组  元素个数
//大堆:向上调整实现升序
void HpBig(int* a, int n)
{
	int i;
	//从第二层的第一孩子开始向上调整建堆
	for (i = 1; i < n; i++)
	{
		AdjustUpBig(a, i);
	}
	int k = n;
	//排序
	for (i = n - 1; i > 0; i--)
	{
		Swp(&a[0], &a[i]);
		k--;
		AdjustDownBig(a, k, 0);
	}
	//打印
	Prin(a, n);
}
//大堆:向下调整实现升序
void HpBig2(int* a, int n)
{
	int i;	
	//向下调整建堆
	for(i = (n - 1-1); i >=0; i--)
	{
		AdjustDownBig(a, n, i);
	}
	int k = n;
	//排序
	for (i = n - 1; i > 0; i--)
	{
		Swp(&a[0], &a[i]);
		k--;
		AdjustDownBig(a, k, 0);
	}
	//打印
	Prin(a, n); 

}

三、降序的实现:通过建小堆实现

>思路:

  1. 将待排序数组构造成一个小堆
  2. 这个序列最小值在堆顶
  3. 将其与末尾元素进行交换,末尾变成最小值
  4. 将剩下的n-1个结点重新调整为小堆
  5. 再次将最小值与此时(为n-1个结点的小堆)的末尾元素交换
  6. 重复下去,到最后就是有序的了,整个数组最大的元素此时在栈顶

1、向上调整算法实现小堆的建立:了解即可

思路一样的,流程图都是大差不差的,无非就是变成了孩子小于爹就交换

2、向下调整算法实现小堆的建立:

3、排序:

都是大堆实现过的,思路就是一样的,就是要注意性质,决定了符号(大于还是小于)

代码:

//因为是直接复制过来的,所以用来Typedef改名
typedef int HpDataType;
//交换数据
void Swp(HpDataType* p1, HpDataType* p2)
{
	assert(p1 && p2);
	HpDataType tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}
//打印
void Prin(int* a, int n)
{
	int i;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
//小堆:向上调整完成降序
void HpSmall(int* a, int n)
{
	int i;
	//从第二层开始调整
	for (i = 1; i < n; i++)
	{
		AdjustUpSmall(a, i);
	}
	int k = n;
	//排序:
	for (i = (n - 1-1); i > 0; i--)
	{
		Swp(&a[0], &a[i]);
		k--;
		AdjustDownSmall(a, k, 0);
	}
	//打印
	Prin(a, n);


}
//小堆:向下调整实现降序
void HpSmall2(int* a, int n)
{
	int i;
	
	//建堆
	for(i = n - 1; i >=0; i--)
	{
		AdjustDownSmall(a, n, i);
	}
	int k = n;
	//排序:
	for (i = n - 1; i > 0; i--)
	{
		Swp(&a[0], &a[i]);
		k--;
		AdjustDownSmall(a, k, 0);
	}
	//打印
	Prin(a, n);
}

四、建堆的时间复杂度计算:

向下调整算法的时间复杂度

时间复杂度为O(N)


向上调整算法的时间复杂度:

计算过程和上面雷同

时间复杂度:O(N*logN)

我们发现这2个不同的特点是:

向下调整:结点数量越多,调整次数越少;(反比)

向上调整:结点数量越多,调整次数越多;(正比)


五、总结:

        对于堆排序的实现,其实只要彻底掌握了堆的实现即可完成,对于向上向下调整算法有了理解,其实堆排序的实现也就不难了,原理都是一样的,非常类似,有了大堆实现升序的思路,降序也就一起出来了,画图更有助于理解。本文图不是很好看,还在努力提升画图技术!!注意的是向上和向下调整建堆的时间复杂度是不一样的,向下调整对于堆排序是最好的选择

  完                  结                           撒                花

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

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

相关文章

find 几招在 Linux 中高效地查找目录

1. 介绍 在 Linux 操作系统中&#xff0c;查找目录是一项常见的任务。无论是系统管理员还是普通用户&#xff0c;都可能需要查找特定的目录以执行各种操作&#xff0c;如导航文件系统、备份数据、删除文件等。Linux 提供了多种命令和工具来帮助我们在文件系统中快速找到目标目…

百度软件测试面试经历,期望薪资27K

一面 1、 请为百度搜索框设计测试用例&#xff1f; 2、百度设计框上线前需要进行那些测试&#xff1f; 界面测试&#xff0c;功能测试&#xff0c;性能测试&#xff0c;安全性测试&#xff0c;易用性测试&#xff0c;兼容性测试&#xff0c;UI测试。 3、如何查看http状态码…

高通 Android 12/13冻结屏幕

冻结屏幕很多第一次听到以为是Android一种异常现象&#xff0c;实则不然&#xff0c;就是防止用户在做一些非法操作导致问题防止安全漏洞问题。 1、主要通过用户行为比如禁止下拉状态栏和按键以及onTouch事件拦截等&#xff0c;不知道请看这篇文章&#xff08;Touch事件传递流…

WPF模板样式Style用法

在Windows Presentation Foundation (WPF) 中&#xff0c;样式&#xff08;Style&#xff09;和模板&#xff08;Template&#xff09;是创建丰富且可重用的UI元素的强大工具。样式允许你定义一组属性设置&#xff0c;这些设置可以应用于一个或多个控件&#xff0c;而模板则允许…

Flink-cdc更好的流式数据集成工具

What’s Flink-cdc? Flink CDC 是基于Apache Flink的一种数据变更捕获技术&#xff0c;用于从数据源&#xff08;如数据库&#xff09;中捕获和处理数据的变更事件。CDC技术允许实时地捕获数据库中的增、删、改操作&#xff0c;将这些变更事件转化为流式数据&#xff0c;并能够…

正反向shell

正反向shell 在实际的应用场景中一般是先找到可以命令执行的漏洞&#xff0c;如果目标主机没有ncat我们要先执行下载ncat命令在被控的服务器上 正向shell 应用场景&#xff1a;在被控端的访问没有限制的时候&#xff0c;控制端向被控端发起了链接&#xff0c;控制端可以是公…

在aspNetCore中 使用System.Text.Json的定制功能, 将定制化的json返回给前端

C# 默认大写, 而大部分的前端默认小写, 这时候可以如此配置: builder.Services.AddControllers().AddJsonOptions((opt) > {opt.JsonSerializerOptions.PropertyNamingPolicy System.Text.Json.JsonNamingPolicy.CamelCase;opt.JsonSerializerOptions.WriteIndented true…

InfLLM的笔记

文件中提供的代码是一个Python函数chat_loop&#xff0c;它是聊天系统的核心循环。以下是对这段代码逻辑的梳理&#xff1a; 函数定义与参数 chat_loop函数接收多个参数&#xff0c;用于配置聊天模型和聊天环境。参数包括模型路径、设备类型、GPU数量、最大GPU内存、数据类型…

安装测缝计安装事项详解

在建筑和工程领域&#xff0c;测量缝隙和裂缝的准确性对于工程质量和安全性至关重要。测缝计作为一种专业的测量工具&#xff0c;能够帮助工程师和施工人员准确测量和监测建筑结构的缝隙情况&#xff0c;进而采取合适的修复和加固措施&#xff0c;保证建筑物的稳定性和安全性。…

Covalent的CQT质押迁移比率在以太坊上升至13%,超Moonbeam记录

Covalent Network&#xff08;CQT&#xff09;作为领先的结构化模块化数据基础设施层&#xff0c;目前其在以太坊上的 CQT 质押比率已超过之前在 Moonbeam 上达到的历史最高水平。自从将质押合约迁移到以太坊不到一个月的时间里&#xff0c;超过总供应量的 13% 的 CQT 代币已被…

Unity中计数器的实现

Unity中计数器的实现 一、前言二、效果与逻辑&#xff08;一&#xff09; 实现效果&#xff08;二&#xff09;功能逻辑 三、功能代码四、应用实现五、结语 一、前言 最近在开发中用到计数器&#xff0c;但是unity自带的UI组件中没有&#xff0c;所以只好自己手撸了一个&#x…

2024电工杯数学建模选题建议及各题思路来啦!

大家好呀&#xff0c;2024电工杯数学建模竞赛开始了&#xff0c;来说一下初步的选题建议吧&#xff1a; 首先定下主基调&#xff0c; 本次电工杯建议选B。A题目难度较高&#xff0c;只建议有相关专业知识和优化经验的队伍选择&#xff0c;小白队伍无脑选B即可。是比较经典的数…

Python数字比大小获取大的数

目录 一、引言 二、数字比较的基本语法 三、获取较大的数 使用条件语句 使用内置函数 四、处理特殊情况 比较非数字类型 处理无穷大和NaN 五、应用实例 在游戏开发中比较分数 在数据分析中找出最大值 六、优化与性能 七、总结 一、引言 在Python编程的广阔天地中…

JS 实现鼠标框选(页面选择)时返回对应的 HTML 或文案内容

JS 实现鼠标框选&#xff08;页面选择&#xff09;时返回对应的 HTML 或文案内容 一、需求背景 1、项目需求 当用户进行鼠标框选选择了页面上的内容时&#xff0c;把选择的内容进行上报。 2、需求解析 虽然这需求就一句话的事&#xff0c;但是很显然&#xff0c;没那么简单…

如何使用maven运行SpringBoot程序?

目录 一、什么是maven 二、什么是SpringBoot 三、如何使用maven运行SpringBoot程序&#xff1f; 一、什么是maven Maven&#xff1a;简化Java项目构建的自动化工具 在软件开发的世界里&#xff0c;Maven以其强大的项目管理和构建自动化功能&#xff0c;为Java开发者提供了…

软件设计师-上午题-计算题汇总

一、存储系统 - 存储容量计算&#xff08;字节编址、位编址、芯片个数&#xff09; 内存地址是16进制 内存地址编址的单位是Byte&#xff0c;1K1024B 1B 8 bit 1.计算存储单元个数 存储单元个数 末地址 - 首地址 1 eg. 按字节编址&#xff0c;地址从 A4000H 到 CBFFFH&…

week2腾讯2019 暑期实习提前批笔试——acwing568. 奇妙的数列

568. 奇妙的数列 判断区间起始位置l的奇偶性&#xff0c;若为偶数&#xff0c;则偶奇交替&#xff0c;一对和为1&#xff0c;反之为-1 然后计算区间内元素对数(r - l 1) / 2&#xff0c;区间元素个数为r - l 1,如果区间内总数为偶数&#xff0c;必然是一正一负刚好成对。如果…

速卖通测评揭秘:如何选择安全的渠道操作

许多商家对测评存在误解&#xff0c;认为只需进行几次测评就能迅速打造爆款。实际上&#xff0c;测评是一个需要计划和持久性的过程&#xff0c;以便让平台检测到产品的受众程度并提高产品的曝光和权重。 在进行测评时&#xff0c;安全是首要考虑的问题。平台可以通过设备、网…

新鲜干货|「隐语城市行·成都站 x 蓉数大讲堂」硬核技术分享、多元场景实践、未来趋势洞察及前沿学术探秘

“隐语”是开源的可信隐私计算框架&#xff0c;内置 MPC、TEE、同态等多种密态计算虚拟设备供灵活选择&#xff0c;提供丰富的联邦学习算法和差分隐私机制 开源项目 github.com/secretflow gitee.com/secretflow 5月18日&#xff0c;「隐语城市行成都站 x 蓉数大讲堂」线下活…

AI绘图副业创收,热门擦边变现赛道怎么玩?网友:瑟瑟才是人类前进的动力!

大家好&#xff0c;我是设计师阿威 今天给大家介绍一个用 AI 搞擦边的变现赛道 而且可以说是0 成本变现的 现在真的越来越多的人都想 0 成本变现&#xff0c;那么 0 成本到底能不能变现&#xff0c;变现的上下限又是多少&#xff1f; 今天这个案例就可以很好的进行说明 可以…