C++实现堆排序实例介绍
作者:NEU! 发布时间:2022-06-05 12:33:54
标签:C++,堆排序
概述:
堆排序是利用构建“堆”的方法确定具有最大值的数据元素,并把该元素与最后位置上的元素交换。可将任意一个由n个数据元素构成的序列按照(a1,a2,...,an),按照从左到右的顺序按层排列构成一棵与该序列对应的完全二叉树。
一棵完全二叉树是一个堆,当且仅当完全二叉树的每棵子树的根值ai≥其左子树的根值a2i,同时ai≥其右子树的根值a 2i+1 (1<i<n/2)。
实现堆排序需要实现两个问题:
如何由无序序列建成一个堆?如何在输出堆顶元素之后,调整剩余元素成为一个新的堆?
思路:
堆排序算法思想:1、从最后一个非叶子节点逐步到树根,对每个子树进行调整堆。
2、重复n-1次如下处理:将堆的根与最后一个叶子交换,除最后一个叶子之外剩余部分再调整为堆。
调整堆算法思想:1、将树根与其左右子树根值最大者交换;(大顶堆)
2、对交换后的左(或右)子树重复过程1,直到左(或右)子树为堆。
时间复杂度:O(nlogn)
代码:
调整堆算法:
void HeapAdjust(int *array,int i,int length){//调整堆
int leftChild=2*i+1;//定义左右孩子
int rightChild=2*i+2;
int max=i;//初始化,假设左右孩子的双亲节点就是最大值
if(leftChild<length&&array[leftChild]>array[max]){
max=leftChild;
}
if(rightChild<length&&array[rightChild]>array[max]){
max=rightChild;
}
if(max!=i){//若最大值不是双亲节点,则交换值
swap(array[max],array[i]);
HeapAdjust(array,max,length);//递归,使其子树也为堆
}
}
堆排序算法:
void HeapSort(int *array,int length){//堆排序
for(int i=length/2-1;i>=0;i--){//从最后一个非叶子节点开始向上遍历,建立堆
HeapAdjust(array,i,length);
}
for(int j=length-1;j>0;j--){//调整堆 ,此处不需要j=0
swap(array[0],array[j]);
HeapAdjust(array,0,j);//因为每交换一次之后,就把最大值拿出(不再参与调整堆),第三个参数应该写j而不是length
Print(array,length);
}
}
完整代码:
//堆排序
#include <iostream>
using namespace std;
void Print(int array[],int length){//每执行一次打印一次序列
for(int i=0;i<length;i++){
cout<<array[i]<<" ";
}
cout<<endl;
}
void HeapAdjust(int *array,int i,int length){//调整堆
int leftChild=2*i+1;//定义左右孩子
int rightChild=2*i+2;
int max=i;//初始化,假设左右孩子的双亲节点就是最大值
if(leftChild<length&&array[leftChild]>array[max]){
max=leftChild;
}
if(rightChild<length&&array[rightChild]>array[max]){
max=rightChild;
}
if(max!=i){//若最大值不是双亲节点,则交换值
swap(array[max],array[i]);
HeapAdjust(array,max,length);//递归,使其子树也为堆
}
}
void HeapSort(int *array,int length){//堆排序
for(int i=length/2-1;i>=0;i--){//从最后一个非叶子节点开始向上遍历,建立堆
HeapAdjust(array,i,length);
}
for(int j=length-1;j>0;j--){//调整堆 ,此处不需要j=0
swap(array[0],array[j]);
HeapAdjust(array,0,j);//因为每交换一次之后,就把最大值拿出(不再参与调整堆),第三个参数应该写j而不是length
Print(array,length);
}
}
int main(){
int array[]={49,38,65,97,76,13,27,49};
int length=sizeof(array)/sizeof(*array);
Print(array,length);//先打印原始序列
HeapSort(array,length);
return 0;
}
运行示例:
第一行是原始序列,第二到八行分别是经过7次调整堆所得到的序列。
来源:https://blog.csdn.net/weixin_59566851/article/details/122075594
0
投稿
猜你喜欢
- 流,就是一系列的数据。当不同介质之间有数据交互的时候,JAVA就使用流来实现。数据源可以是文件,还可以是数据库、网络甚至其他的程序。比如读取
- Java停止线程的逻辑(协同、通知)在Java程序中,我们想要停止一个线程可以通过interrupt方法进行停止。但是当我们调用interr
- 前言今天主要讲的是如何把通过接口获取到的Xml数据转换成(反序列化)我们想要的实体对象,当然Xml反序列化和Json反序列化的方式基本上都是
- JDBC操作MySQL在实际的企业级开发环境中,如果数据规模特S别大,此时采用传统的SQL语句去处理的话一般需要分成很多批次处理,而且很容易
- 请求转发的三种方式SpringMVC请求转发区别于重定向,请求转发地址栏不会发生改变、只发送一次请求、能携带原有的参数,但只可以在同一个服务
- 一、概述1、XMLReader为抽象类,其派生类有:XmlDictionaryReaderXmlNodeReaderXmlTextReade
- 依赖配置结合前面的内容,这里我们要嵌入数据库的操作,这里以操作MySQL为例整合Mybatis,首先需要在原来的基础上添加以下依赖<!
- *注:可以用 adb logcat > 路径/文件名 来保存,此命令执行之时起的全部日志信息到一个文件里,ctrl + C 结束日志输
- 类和对象的关系类就是一类对象的统称。对象就是这一类具体化的一个实例。 (对象是类的实例化)对象是什么?此对象非彼对象!!!😂说到对象就要提到
- 最近在研究断点下载(下载续传)的功能,此功能需要服务端和客户端进行对接编写,本篇也是记录一下关于贴上关于实现服务端(Spring Boot)
- Ajax本质上和普通的HTTP请求是一样的,只不过普通的HTTP请求是给人看的,而Ajax请求是给JS代码去用的。所以Ajax请求的页面一般
- rocketmq client 日志的问题处理使用rocketmq后,默认会在{user.home}\logs\rocketmqlogs 目
- 1、找奇数:public static boolean isOdd(int i){ return i % 2 == 1; }上面的方法真
- 一、使用策略枚举来优化if-else看到网上蛮多人推荐使用策略模式来优化if-else,但我总觉得,搞一堆策略类来优化大批量if-else,
- 支持趋势线的图表类型包括二维面积图、条形图、柱形图、柱形图、股价图、xy (散点图) 和气泡图中;不能向三维、堆积、雷达图、饼图、曲面图或圆
- 在学习MyBatis过程中想实现模糊查询,可惜失败了。后来上百度上查了一下,算是解决了。记录一下MyBatis实现模糊查询的几种方式。 数据
- MyBatis @MapKey的妙用背景在实际开发中,有一些场景需要我们返回主键或者唯一键为Key、Entity为Value的Map集合,如
- 前言一般生成的PDF文档默认的文档底色为白色,我们可以通过一定方法来更改文档的背景色,以达到文档美化以及保护双眼的作用。 以下内容提供了Ja
- 关于这个的例子其实网上已经有这方面的资料了,但是为了文章的完整性,还是觉得有必要讲解.我们先来看一下效果:  
- 实时代码模板(Live Templates)我们先来看一个gif图:大兄弟,你看清我的操作了么?这个就是实时代码模板的功能。我们来看一下怎么