首页 > 其他分享 >堆排序的实现

堆排序的实现

时间:2024-07-19 20:27:47浏览次数:16  
标签:arr end parent 23 实现 堆排序 int child

首先需要知道的是,如果想要对一个数组排升序,要建大堆,排降序,要建小堆。

具体过程:(以排降序为例)

1)建小堆;

2)交换堆顶(第一个)和堆尾(最后一个)的数据;

3)交换完后,最后一个数据不动,剩下的数据对堆顶元素进行向下调整;

4)循环2)3)步骤。

下面用图来展示一下过程:

1)假设对数组arr[10] = {3,1,5,23,64,7,45,37,9,23}进行排序,建好的小堆如图:

dec52651be4d451aa46499df46e727c1.png

2)交换堆顶和堆尾的数据,

66efa9e8e1f8421eab9a42746bc1770a.png

3)对64进行向下调整,进行向下调整时,不将堆尾的1算入数组,那么就是对下图进行调整:

7da5935cac474919b477182a99f10016.png

因为只换了堆顶和堆尾,堆顶的左右子树仍然是小堆,所以可以直接对堆顶调整:

ef3a88bbd7c243759ed97e677249d8a7.png

这里的黄色框内表示没有参与调整。

继续交换:

8f39514ff7574491b9ed06fbd0960495.png

交换完继续对堆顶调整,调整时对下图框外数据调整:

dbcef34a0dbb4e809db0e63d7449e45d.png

以此循环进行,最终实现排序。

部分流程图如下:

fbf218245b684e8699919d638674342c.png

最终得到:

7412b508984648498df2bbc039e031ae.png

以数组形式来看就是{64,45,37,23,23,9,7,5,3,1};实现了降序。

参考代码如下:

void AdjustDown(int* a, int k, int parent)
{
	int child = 2 * parent + 1;

	while (child < k)
	{
		//找左右孩子小的那一个
		if (child + 1 < k && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
int main()
{
    int arr[10] = {3,1,5,23,64,7,45,37,9,23};
    int k = sizeof(arr)/sizeof(arr[0]);
    int i = 0;
    for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr,k,i);
	}
	int end = n - 1;
	while(end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}

 

 

 

标签:arr,end,parent,23,实现,堆排序,int,child
From: https://blog.csdn.net/guaiguaiyalj/article/details/140417501

相关文章

  • JavaScript实现通过按纽控制电梯上下移动,并实现帧频动画
    varapp=newPIXI.Application(520,460);document.body.appendChild(app.view);//创建背景varbg=newPIXI.Sprite.fromImage("res/lianxi/elevator/bg.png");app.stage.addChild(bg);varelevator=newPIXI.Sprite.fromImage("res/lianxi/elevator/dt......
  • 第4章.消费者领域中的模式实现
            我们在前几章中学习了重要的建筑模式;本章介绍了与消费者领域相关的这些模式的用例。尽管消费者领域存在许多用例(电子健康、老年护理、宠物追踪、能源管理、安全保障、机器人吸尘器等),但本章仅详细介绍两个用例——家庭自动化和智能煮蛋器——以透视实施消费者物......
  • 顺序表实现队列(c语言)
    队列概念篇图示代码篇1.队列的声明2.队列的创建3.队列的销毁4.队列扩容5.入列6.出列6.队首元素7.队列的元素个数完整代码运行结果建议你在看这篇文章先看一下顺序表知识。我在这里通过顺序表的写法实现先进先出的特征来实现队列。当然顺序表也可以实现栈,感......
  • 弹性伸缩:如何在Eureka中实现服务的自动扩展和收缩
    弹性伸缩:如何在Eureka中实现服务的自动扩展和收缩在微服务架构中,服务的自动扩展和收缩是实现高可用性和成本效益的关键策略。Eureka,作为Netflix开源的服务发现框架,虽然本身不直接提供自动扩展和收缩的功能,但我们可以通过一些策略和工具来实现。本文将详细解释如何在Eureka......
  • python+flask计算机毕业设计基于WEB技术的校园红歌曲库管理系统的设计与实现(程序+开题
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着信息技术的飞速发展和互联网的广泛普及,数字化管理已成为提升工作效率与服务质量的重要手段。在校园文化建设中,红歌作为传承红色文化、......
  • 链表(Linked List)-Python实现-使用类和使用函数
    链表链表(LinkedList)单链表(SinglyLinkedList)节点类(NodeClass)链表类(LinkedListClass)使用链表类不用类的方法实现链表实现单链表使用函数实现链表具体讲解类的方法实现链表Node类LinkedList类不用类的方法实现链表创建节点添加节点删除节点搜索节点显示链表总......
  • python实现爆破wifi密码
    importpywifiimporttimefrompywifiimportconst#WiFi扫描模块defwifi_scan():#初始化wifiwifi=pywifi.PyWiFi()#使用第一个无线网卡interface=wifi.interfaces()[0]#开始扫描interface.scan()foriinrange(4):t......
  • 02-使用BIOS中断 显示字符/读取磁盘 【实现boot中加载loader的功能】
    bios提供了一组服务,可以帮助我们操纵硬件,避免我们直接与硬件细节打交道当触发软中断时,会自动从中断向量表中取出想用的中断程序的首地址,来执行中断程序,参数通过寄存器传递一、Bios的INT10中断INT10中断是BIOS用于控制显示屏的关键接口,包括设置显示器模式、光标管理和显......
  • 基于 CNN(二维卷积Conv2D)+LSTM 实现股票多变量时间序列预测(PyTorch版)
    前言系列专栏:【深度学习:算法项目实战】✨︎涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域,讨论了各种复杂的深度神经网络思想,如卷积神经网络、循环神经网络、生成对抗网络、门控循环单元、长短期记忆......
  • Cookie、Session、JWT在koa中的应用及实现原理
    Cookie、Session、JWT在koa中的应用及实现原理  目录Cookie重要属性实现原理cookie签名实现原理注意事项Session实现原理JWT使用方式组成实际应用实现原理前端存储方式cookiesessionlocalStoragesessionStoragetoken区别 CookieHTTP......