C语言 数据结构堆排序顺序存储（升序）

概述堆排序顺序存储（升序）一： 完全二叉树的概念：前h-1层为满二叉树，最后一层连续缺失右结点！

堆排序顺序存储（升序）

一： 完全二叉树的概念：前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语言 数据结构堆排序顺序存储（升序）全部内容，希望文章能够帮你解决C语言 数据结构堆排序顺序存储（升序）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。