C语言中怎么实现堆排序顺序存储
这篇文章将为大家详细讲解有关C语言中怎么实现堆排序顺序存储,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。
10年积累的做网站、成都网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站设计后付款的网站建设流程,更有东阿免费网站建设让你可以放心的选择与我们合作。
堆排序顺序存储(升序)
一: 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点!
二:首先堆是一棵全完二叉树:
a:构建一个堆分为两步:⑴创建一棵完全二叉树 ⑵调整为一个堆
(标注:大根堆为升序,小根堆为降序)
b:算法描述:①创建一棵完全二叉树
②while(有双亲){
A:调整为大根堆;
B:交换根和叶子结点;
C:砍掉叶子结点;
}
c:时间复杂度为 O(nlogn) ,空间复杂度为 O(1), 是不稳定排序!
代码实现:
/*堆排序思想:[完全二叉树的定义:前 h-1 层为满二叉树一最后一层连续缺失右结点(即右子女)],(大根堆升序排序,小根堆降序排列) 首先堆是一个完全二叉树 ,根据数组下标就可建成了一棵完全二叉树 其次:while(有双亲){ A: 调整为一个大根堆 【Adjust()函数实现】 B: 交换最后一个叶子结点和根结点 【Swap()函数实现】 C: 砍掉最后一个叶子结点 【即元素个数 n--】 } */ #include#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]2){ //保证有双亲结点 Adjust(); //调整大根堆函数 Swap(&b[1],&b[n-1]); //将最后一个叶子结点和根结点交换 n--; //裁剪最后的叶子结点 } } int main(void){ int i,m; cout<<"请输入数据的总数【0单元不要,实际元素个数为(n-1)个】:"< >n; m=n; cout<<"请输入各个数据【0单元不要,实际元素个数为(n-1)个】:"< >b[i]; } HeapSort(); //堆排序 cout<<"大根堆升序排列为:"< 关于C语言中怎么实现堆排序顺序存储就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
当前文章:C语言中怎么实现堆排序顺序存储
分享网址:http://myzitong.com/article/jcsdco.html