C语言 数据结构堆排序顺序存储（升序）
堆排序顺序存储（升序）
一： 完全二叉树的概念：前h-1层为满二叉树，最后一层连续缺失右结点！
二：首先堆是一棵全完二叉树：
a:构建一个堆分为两步：⑴创建一棵完全二叉树 ⑵调整为一个堆
（标注：大根堆为升序，小根堆为降序）
b:算法描述：①创建一棵完全二叉树
②while(有双亲){
A:调整为大根堆；
B:交换根和叶子结点；
C:砍掉叶子结点；
}
c:时间复杂度为O(nlogn) ,空间复杂度为O(1),是不稳定排序！
代码实现：
/*堆排序思想:[完全二叉树的定义:前h-1层为满二叉树一最后一层连续缺失右结点(即右子女)]，(大根堆升序排序，小根堆降序排列)
首先堆是一个完全二叉树，根据数组下标就可建成了一棵完全二叉树
其次:while(有双亲){
A:调整为一个大根堆【Adjust()函数实现】
B:交换最后一个叶子结点和根结点【Swap()函数实现】
C:砍掉最后一个叶子结点【即元素个数n--】
}
*/
#include
#defineN100
usingnamespacestd;
intb[N]={0};//存储数据的数组
intn=0;//记录数据的总个数【0单元不要,实际元素个数为(n-1)个】
voidSwap(int*x,int*y){
intt;
t=*x;
*x=*y;
*y=t;
}
voidAdjust(){
intp;//记录双亲结点
inttag=1;//记录是否已经调整为大根堆(标志性的变量)
while(tag){//判断是否已经调整好为大根堆
p=(n-1)/2;//最后一个双亲结点的下标
tag=0;//凡是交换后，tag=1,标志着还没有调整为大根堆，否则继续调整
while(p>0){//确保有双亲结点
if(b[p]2){//保证有双亲结点
Adjust();//调整大根堆函数
Swap(&b[1],&b[n-1]);//将最后一个叶子结点和根结点交换
n--;//裁剪最后的叶子结点
}
}
intmain(void){
inti,m;
cout<<"请输入数据的总数【0单元不要,实际元素个数为(n-1)个】:"<>n;
m=n;
cout<<"请输入各个数据【0单元不要,实际元素个数为(n-1)个】:"<>b[i];
}
HeapSort();//堆排序
cout<<"大根堆升序排列为:"<
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！