C语言 数据结构堆排序顺序存储(升序)

堆排序顺序存储(升序)

一: 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点!

二:首先堆是一棵全完二叉树:

a:构建一个堆分为两步:⑴创建一棵完全二叉树      ⑵调整为一个堆

(标注:大根堆为升序,小根堆为降序)

   b:算法描述:①创建一棵完全二叉树  

②while(有双亲){

A:调整为大根堆;

B:交换根和叶子结点;

C:砍掉叶子结点;

}

  c:时间复杂度为 O(nlogn)  ,空间复杂度为 O(1), 是不稳定排序!

代码实现:

/*堆排序思想:[完全二叉树的定义:前 h-1 层为满二叉树一最后一层连续缺失右结点(即右子女)],(大根堆升序排序,小根堆降序排列)

首先堆是一个完全二叉树 ,根据数组下标就可建成了一棵完全二叉树

其次:while(有双亲){

A: 调整为一个大根堆 【Adjust()函数实现】

B: 交换最后一个叶子结点和根结点 【Swap()函数实现】

C: 砍掉最后一个叶子结点 【即元素个数 n--】

}

*/

#include <iostream>

#define N 100

using namespace std;

int b[N]={0}; //存储数据的数组

int n=0; //记录数据的总个数【0单元不要,实际元素个数为(n-1)个】

void Swap(int *x,int *y){

int t;

t=*x;

*x=*y;

*y=t;

}

void Adjust(){

int p; //记录双亲结点

int tag=1; //记录是否已经调整为大根堆(标志性的变量)

while(tag){ //判断是否已经调整好为大根堆

p=(n-1)/2; //最后一个双亲结点的下标

tag=0; //凡是交换后,tag=1,标志着还没有调整为大根堆,否则继续调整

while(p>0){ //确保有双亲结点

if(b[p]<b[2*p]){ //若根结点大于左子女结点,就交换

Swap(&b[p],&b[2*p]);

tag=1;

}

if(2*p+1<n && b[p]<b[2*p+1]){ //若存在右子女,并且根结点大于右子女结点,就交换

Swap(&b[p],&b[2*p+1]);

tag=1;

}

p--; //直到最后一个双亲结点调整完

}

}

}

void HeapSort(){

while(n>2){ //保证有双亲结点

Adjust(); //调整大根堆函数

Swap(&b[1],&b[n-1]); //将最后一个叶子结点和根结点交换

n--; //裁剪最后的叶子结点

}

}

int main(void){

int i,m;

cout<<"请输入数据的总数【0单元不要,实际元素个数为(n-1)个】:"<<endl;

cin>>n;

m=n;

cout<<"请输入各个数据【0单元不要,实际元素个数为(n-1)个】:"<<endl;

b[0]=0;

for(i=1;i<n;i++){

cin>>b[i];

}

HeapSort(); //堆排序

cout<<"大根堆升序排列为:"<<endl;

for(i=1;i<m;i++){

cout<<b[i]<<" ";

}

cout<<endl;

return 0;

}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

以上是 C语言 数据结构堆排序顺序存储(升序) 的全部内容, 来源链接: utcz.com/z/313916.html

回到顶部