簡單算法———堆排序

2019-11-11 04:54:02

字體：大中小

供稿：網(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é)點中較大的結(jié)點 if(nChild < nlength-1 && array[nChild+1]>array[nChild]) nChild++; ///如果較大的子結(jié)點大于父結(jié)點那么把較大的子結(jié)點往上移動，替換它的父結(jié)點 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)整完之后第一個元素是序列的最大的元素 ///（前半部分元素中的孩子節(jié)點是后半部分元素） ///length/2-1是最后一個非葉節(jié)點，此處"/"為整除 for(i=length/2-1;i>=0;--i) { HeapAdjust(array,i,length); } ///從最后一個元素開始對序列進(jìn)行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個元素 for(i=length-1;i>0;--i) { ///把第一個元素和當(dāng)前的最后一個元素交換， ///保證當(dāng)前的最后一個位置的元素都是在現(xiàn)在的這個序列之中最大的 //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)整完畢保證第一個元素是當(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;}

上一篇：從JVM看性能分析與設(shè)計

下一篇：OpenCV學(xué)習(xí)筆記（03）：圖像ROI以及線性混合