您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

排序---堆排序

时间:2019-10-30 10:11:30  来源:  作者:

一:定义

作为选择排序的改进版,堆排序可以把每一趟元素的比较结果保存下来,以便我们在选择最小/大元素时对已经比较过的元素做出相应的调整。

二:堆排序算法

作为选择排序的改进版,堆排序可以把每一趟元素的比较结果保存下来,以便我们在选择最小/大元素时对已经比较过的元素做出相应的调整。

堆排序是一种树形选择排序,在排序过程中可以把元素看成是一颗完全二叉树,每个节点都大(小)于它的两个子节点,当每个节点都大于等于它的两个子节点时,就称为大顶堆,也叫堆有序; 当每个节点都小于等于它的两个子节点时,就称为小顶堆。

排序---堆排序

 


排序---堆排序

 

下面是我们要保存在数组中的堆的形式

排序---堆排序

 

二:堆排序算法

1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
 
2.将根节点与尾节点交换并输出此时的尾节点
 
3.将剩余的n -1个节点重新进行堆有序化
 
4.重复步骤2,步骤3直至构造成一个有序序列

三:图解演示,构造堆(大顶堆)

{5, 2, 6, 0, 3, 9, 1, 7, 4, 8}
排序---堆排序

 

在构造有序堆时,我们开始只需要扫描一半的元素(n/2-1 ~ 0)即可,为什么?

因为(n/2-1)~0的节点才有子节点,如图1,n=8,(n/2-1) = 3 即3 2 1 0这个四个节点才有子节点

第一次找到[n/2]处,进行构造:

排序---堆排序

 

我们比较父节点,左右孩子结点的大小,将最大的作为堆顶

第二次,我们对上次找到位置-1即可,找到结点0,对其左右孩子比较,构造这三个结点的最大堆

排序---堆排序

 

第三次,我们找到结点6,要对其进行构造,结果如下

排序---堆排序

 

第四次(重点),我们不止要构造双亲和左右孩子,我们还要比较其孩子结点为根的堆是否正确,不然我们需要进行调整

排序---堆排序

 

我们发现将8,7,2三个结点变为了最大堆,但是其中2,3子树不再是一个最大堆,我们需要对其修改

排序---堆排序

 

第五次:选取结点9进行构造

排序---堆排序

 

发现以结点5为根的子树不是最大堆,我们需要进行调整

排序---堆排序

 

完成最大堆的构建

排序---堆排序

 

四:图解演示:堆排序(堆存储在数组中)

第一步:将最大值和最后的一个元素交换

排序---堆排序

 

第二步:将剩余的结点再次进行堆构造

排序---堆排序

 

第三步:参照第一步

排序---堆排序

 

按照上面循环,最终结果为

排序---堆排序

 

五:代码实现

void swap(int K[], int i, int j)
{
 int temp = K[i];
 K[i] = K[j];
 K[j] = temp;
}
//大顶堆的构造,传入的i是父节点
void HeapAdjust(int k[],int p,int n)
{
 int i,temp;
 temp = k[p];
 for (i = 2 * p; i <= n;i*=2) //逐渐去找左右孩子结点
 {
 //找到两个孩子结点中最大的
 if (i < n&&k[i] < k[i + 1])
 i++;
 //父节点和孩子最大的进行判断,调整,变为最大堆
 if (temp >= k[i])
 break;
 //将父节点数据变为最大的,将原来的数据还是放在temp中,
 k[p] = k[i]; //若是孩子结点的数据更大,我们会将数据上移,为他插入的点提供位置
 p = i;
 }
 //当我们在for循环中找到了p子树中,满足条件的点,我们就加入数据到该点p,注意:p点原来数据已经被上移动了
 //若没有找到,就是相当于对其值不变
 //插入
 k[p] = temp;
}
//大顶堆排序
void HeapSort(int k[], int n)
{
 int i;
 //首先将无序数列转换为大顶堆
 for (i = n / 2; i > 0;i--) //注意由于是完全二叉树,所以我们从一半向前构造,传入父节点
 HeapAdjust(k, i, n);
 //上面大顶堆已经构造完成,我们现在需要排序,每次将最大的元素放入最后
 //然后将剩余元素重新构造大顶堆,将最大元素放在剩余最后
 for (i = n; i >1;i--)
 {
 swap(k, 1, i);
 HeapAdjust(k, 1, i - 1);
 }
}
int main()
{
 int i;
 int a[11] = {-1, 5, 2, 6, 0, 3, 9, 1, 7, 4, 8 };
 HeapSort(a, 10);
 for (i = 1; i <= 10; i++)
 printf("%d ", a[i]);
 system("pause");
 return 0;
}

六:性能分析

运行时间主要消耗在构造堆和重建堆时的反复筛选上。
构造堆的时间复杂度为O(n)
重建堆时时间复杂度为O(nlogn)。
所以总体就是O(nlogn)。
不适合排序序列个数较少的情况


Tags:堆排序   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1. 插入排序步骤:1.从第一个元素开始,该元素可以认为已经被排序2.取下一个元素tem,从已排序的元素序列从后往前扫描3.如果该元素大于tem,则将该元素移到下一位4.重复步骤3,直到找...【详细内容】
2021-08-19  Tags: 堆排序  点击:(100)  评论:(0)  加入收藏
一:定义作为选择排序的改进版,堆排序可以把每一趟元素的比较结果保存下来,以便我们在选择最小/大元素时对已经比较过的元素做出相应的调整。二:堆排序算法作为选择排序的改进版,...【详细内容】
2019-10-30  Tags: 堆排序  点击:(60)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条