簡單算法———堆排序

2019-11-11 05:27:41

字體：大中小

來源：轉載

供稿：網友

#include <stdio.h>#include <stdlib.h>///array是待調整的堆數組，i是待調整的數組元素的位置，nlength是數組的長度///本函數功能是：根據數組array構建大根堆void HeapAdjust(int array[],int i,int nlength){ int nChild; int temp; for(;2*i+1<nlength;i=nChild) { nChild = 2*i+1; ///得到子結點中較大的結點 if(nChild < nlength-1 && array[nChild+1]>array[nChild]) nChild++; ///如果較大的子結點大于父結點那么把較大的子結點往上移動，替換它的父結點 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; ///調整序列的前半部分元素，調整完之后第一個元素是序列的最大的元素 ///（前半部分元素中的孩子節點是后半部分元素） ///length/2-1是最后一個非葉節點，此處"/"為整除 for(i=length/2-1;i>=0;--i) { HeapAdjust(array,i,length); } ///從最后一個元素開始對序列進行調整，不斷的縮小調整的范圍直到第一個元素 for(i=length-1;i>0;--i) { ///把第一個元素和當前的最后一個元素交換， ///保證當前的最后一個位置的元素都是在現在的這個序列之中最大的 //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; ///不斷縮小調整heap的范圍，每一次調整完畢保證第一個元素是當前序列的最大值 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;}

上一篇：[校內互測]最大（二分+線段樹||bitset）

下一篇：編程練習三