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

堆排序顺序存储（升序）

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

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

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

（标注：大根堆为升序，小根堆为降序）

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

②while(有双亲){
A:调整为大根堆；
B:交换根和叶子结点；
C:砍掉叶子结点；
}

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

代码实现：

 
 
#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<<"大根堆升序排列为:"<

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