简单算法———堆排序

2019-11-11 05:30: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;}

上一篇：《剑指offer》 NO.9 变态跳台阶

下一篇：Chapter_3表、栈和队列：栈

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注