簡單算法———堆排序

2019-11-11 05:30:41

字體：大中小

供稿：網(wǎng)友

#include <stdio.h>#include <stdlib.h>///array是待調(diào)整的堆數(shù)組，i是待調(diào)整的數(shù)組元素的位置，nlength是數(shù)組的長度///本函數(shù)功能是：根據(jù)數(shù)組array構(gòu)建大根堆void HeapAdjust(int array[],int i,int nlength){ int nChild; int temp; for(;2*i+1<nlength;i=nChild) { nChild = 2*i+1; ///得到子結(jié)點(diǎn)中較大的結(jié)點(diǎn) if(nChild < nlength-1 && array[nChild+1]>array[nChild]) nChild++; ///如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng)，替換它的父結(jié)點(diǎn) if(array[i]<array[nChild]) { temp=array[i]; array[i]=array[nChild]; array[nChild]=temp; } else break; }}void HeapSort(int array[] , int length){ int i; int temp; ///調(diào)整序列的前半部分元素，調(diào)整完之后第一個(gè)元素是序列的最大的元素 ///（前半部分元素中的孩子節(jié)點(diǎn)是后半部分元素） ///length/2-1是最后一個(gè)非葉節(jié)點(diǎn)，此處"/"為整除 for(i=length/2-1;i>=0;--i) { HeapAdjust(array,i,length); } ///從最后一個(gè)元素開始對(duì)序列進(jìn)行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個(gè)元素 for(i=length-1;i>0;--i) { ///把第一個(gè)元素和當(dāng)前的最后一個(gè)元素交換， ///保證當(dāng)前的最后一個(gè)位置的元素都是在現(xiàn)在的這個(gè)序列之中最大的 //array[i]=array[0]^array[i]; //array[0]=array[0]^array[i]; //array[i]=array[0]^array[i]; temp = array[i]; array[i] = array[0]; array[0] = temp; ///不斷縮小調(diào)整heap的范圍，每一次調(diào)整完畢保證第一個(gè)元素是當(dāng)前序列的最大值 HeapAdjust(array,0,i); }}int main(){ int i; int num[]={9,8,5,84,23,1,585,2,1,0}; HeapSort(num,sizeof(num)/sizeof(int)); for(i=0;i<sizeof(num)/sizeof(int);i++) { PRintf("%d ",num[i]); } printf("/nok/n"); return 0;}

上一篇：《劍指offer》 NO.9 變態(tài)跳臺(tái)階

下一篇：Chapter_3表、棧和隊(duì)列：棧