C語言中怎么實現(xiàn)堆排序順序存儲

這篇文章將為大家詳細(xì)講解有關(guān)C語言中怎么實現(xiàn)堆排序順序存儲，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

10年積累的做網(wǎng)站、成都網(wǎng)站建設(shè)經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有東阿免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

堆排序順序存儲（升序）

一：完全二叉樹的概念：前h-1層為滿二叉樹，最后一層連續(xù)缺失右結(jié)點！

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

a:構(gòu)建一個堆分為兩步：⑴創(chuàng)建一棵完全二叉樹 ⑵調(diào)整為一個堆

（標(biāo)注：大根堆為升序，小根堆為降序）

b:算法描述：①創(chuàng)建一棵完全二叉樹

②while(有雙親){
A:調(diào)整為大根堆；
B:交換根和葉子結(jié)點；
C:砍掉葉子結(jié)點；
}

c:時間復(fù)雜度為 O(nlogn) ,空間復(fù)雜度為 O(1), 是不穩(wěn)定排序！

代碼實現(xiàn)：

/*堆排序思想:[完全二叉樹的定義:前 h-1 層為滿二叉樹一最后一層連續(xù)缺失右結(jié)點(即右子女)]，(大根堆升序排序，小根堆降序排列) 
  首先堆是一個完全二叉樹 ，根據(jù)數(shù)組下標(biāo)就可建成了一棵完全二叉樹 
  其次:while(有雙親){ 
    A: 調(diào)整為一個大根堆         【Adjust()函數(shù)實現(xiàn)】 
    B: 交換最后一個葉子結(jié)點和根結(jié)點    【Swap()函數(shù)實現(xiàn)】 
    C: 砍掉最后一個葉子結(jié)點      【即元素個數(shù) n--】 
  } 
*/ 
 
#include <iostream> 
#define N 100 
 
using namespace std;  
 
int b[N]={0};    //存儲數(shù)據(jù)的數(shù)組  
int n=0;      //記錄數(shù)據(jù)的總個數(shù)【0單元不要,實際元素個數(shù)為(n-1)個】 
 
void Swap(int *x,int *y){ 
  int t; 
  t=*x; 
  *x=*y; 
  *y=t; 
}  
 
void Adjust(){ 
  int p;         //記錄雙親結(jié)點  
  int tag=1;       //記錄是否已經(jīng)調(diào)整為大根堆(標(biāo)志性的變量) 
  while(tag){       //判斷是否已經(jīng)調(diào)整好為大根堆 
    p=(n-1)/2;     //最后一個雙親結(jié)點的下標(biāo) 
    tag=0;       //凡是交換后，tag=1,標(biāo)志著還沒有調(diào)整為大根堆，否則繼續(xù)調(diào)整  
    while(p>0){     //確保有雙親結(jié)點 
      if(b[p]<b[2*p]){     //若根結(jié)點大于左子女結(jié)點，就交換  
        Swap(&b[p],&b[2*p]); 
        tag=1; 
      } 
      if(2*p+1<n && b[p]<b[2*p+1]){ //若存在右子女，并且根結(jié)點大于右子女結(jié)點，就交換  
        Swap(&b[p],&b[2*p+1]); 
        tag=1;      
      } 
      p--;        //直到最后一個雙親結(jié)點調(diào)整完  
    }  
  }  
} 
 
void HeapSort(){ 
  while(n>2){         //保證有雙親結(jié)點  
    Adjust();        //調(diào)整大根堆函數(shù) 
    Swap(&b[1],&b[n-1]);  //將最后一個葉子結(jié)點和根結(jié)點交換  
    n--;          //裁剪最后的葉子結(jié)點  
  } 
}   
    
int main(void){ 
  int i,m; 
  cout<<"請輸入數(shù)據(jù)的總數(shù)【0單元不要,實際元素個數(shù)為(n-1)個】:"<<endl; 
  cin>>n; 
  m=n; 
  cout<<"請輸入各個數(shù)據(jù)【0單元不要,實際元素個數(shù)為(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; 
}

關(guān)于C語言中怎么實現(xiàn)堆排序順序存儲就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

新聞名稱：C語言中怎么實現(xiàn)堆排序順序存儲
轉(zhuǎn)載源于：http://bm7419.com/article20/jcsdco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、微信小程序、電子商務(wù)、用戶體驗、ChatGPT、服務(wù)器托管

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容