程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C語言 數據結構堆排序順序存儲(升序)

C語言 數據結構堆排序順序存儲(升序)

編輯:關於C++

C語言 數據結構堆排序順序存儲(升序)。本站提示廣大學習愛好者:(C語言 數據結構堆排序順序存儲(升序))文章只能為提供參考,不一定能成為您想要的結果。以下是C語言 數據結構堆排序順序存儲(升序)正文


C語言 數據結構堆排序順序存儲(升序)

投稿:lqh

這篇文章主要介紹了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; 
} 

感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved