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; }
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!