您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)C語言中怎么實(shí)現(xiàn)堆排序順序存儲,文章內(nèi)容質(zhì)量較高,因此小編分享給大家做個參考,希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。
堆排序順序存儲(升序)
一: 完全二叉樹的概念:前h-1層為滿二叉樹,最后一層連續(xù)缺失右結(jié)點(diǎn)!
二:首先堆是一棵全完二叉樹:
a:構(gòu)建一個堆分為兩步:⑴創(chuàng)建一棵完全二叉樹 ⑵調(diào)整為一個堆
(標(biāo)注:大根堆為升序,小根堆為降序)
b:算法描述:①創(chuàng)建一棵完全二叉樹
②while(有雙親){
A:調(diào)整為大根堆;
B:交換根和葉子結(jié)點(diǎn);
C:砍掉葉子結(jié)點(diǎn);
}
c:時間復(fù)雜度為 O(nlogn) ,空間復(fù)雜度為 O(1), 是不穩(wěn)定排序!
代碼實(shí)現(xiàn):
/*堆排序思想:[完全二叉樹的定義:前 h-1 層為滿二叉樹一最后一層連續(xù)缺失右結(jié)點(diǎn)(即右子女)],(大根堆升序排序,小根堆降序排列) 首先堆是一個完全二叉樹 ,根據(jù)數(shù)組下標(biāo)就可建成了一棵完全二叉樹 其次:while(有雙親){ A: 調(diào)整為一個大根堆 【Adjust()函數(shù)實(shí)現(xiàn)】 B: 交換最后一個葉子結(jié)點(diǎn)和根結(jié)點(diǎn) 【Swap()函數(shù)實(shí)現(xiàn)】 C: 砍掉最后一個葉子結(jié)點(diǎn) 【即元素個數(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í)際元素個數(shù)為(n-1)個】 void Swap(int *x,int *y){ int t; t=*x; *x=*y; *y=t; } void Adjust(){ int p; //記錄雙親結(jié)點(diǎn) int tag=1; //記錄是否已經(jīng)調(diào)整為大根堆(標(biāo)志性的變量) while(tag){ //判斷是否已經(jīng)調(diào)整好為大根堆 p=(n-1)/2; //最后一個雙親結(jié)點(diǎn)的下標(biāo) tag=0; //凡是交換后,tag=1,標(biāo)志著還沒有調(diào)整為大根堆,否則繼續(xù)調(diào)整 while(p>0){ //確保有雙親結(jié)點(diǎn) if(b[p]<b[2*p]){ //若根結(jié)點(diǎn)大于左子女結(jié)點(diǎn),就交換 Swap(&b[p],&b[2*p]); tag=1; } if(2*p+1<n && b[p]<b[2*p+1]){ //若存在右子女,并且根結(jié)點(diǎn)大于右子女結(jié)點(diǎn),就交換 Swap(&b[p],&b[2*p+1]); tag=1; } p--; //直到最后一個雙親結(jié)點(diǎn)調(diào)整完 } } } void HeapSort(){ while(n>2){ //保證有雙親結(jié)點(diǎn) Adjust(); //調(diào)整大根堆函數(shù) Swap(&b[1],&b[n-1]); //將最后一個葉子結(jié)點(diǎn)和根結(jié)點(diǎn)交換 n--; //裁剪最后的葉子結(jié)點(diǎn) } } int main(void){ int i,m; cout<<"請輸入數(shù)據(jù)的總數(shù)【0單元不要,實(shí)際元素個數(shù)為(n-1)個】:"<<endl; cin>>n; m=n; cout<<"請輸入各個數(shù)據(jù)【0單元不要,實(shí)際元素個數(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語言中怎么實(shí)現(xiàn)堆排序順序存儲就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,可以學(xué)到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。