堆排序
思想：
1.构建最大堆
2.把根节点和最后一个节点交换，,把堆长度-1，也就不考虑放最后的最大的元素了，再构建最大堆
3.现在第二大的元素在根节点了，我们再重复步骤2，直到堆长度为1
int MaxHeap(int DataArray[],int Father,int DataLen){ int LeftSon=Father<<1; int RightSon=LeftSon+1; int largest=Father; if(LeftSon<=DataLen&&DataArray[LeftSon]>DataArray[Father]){ largest=LeftSon; } if(RightSon<=DataLen&&DataArray[RightSon]>DataArray[largest]){ largest=RightSon; } if(largest!=Father){ int tem=DataArray[Father]; DataArray[Father]=DataArray[largest]; DataArray[largest]=tem; MaxHeap(DataArray,largest,DataLen); } } int BuildHeap(int DataArray[],int DataLen){ for(int i=DataLen>>1;i>=1;i--) MaxHeap(DataArray,i,DataLen); } int HeapSort(int DataArray[],int DataLen){ BuildHeap(DataArray,DataLen); int tmp; for(int i=DataLen;i>=2;i--){ tmp=DataArray[i]; DataArray[i]=DataArray[1]; DataArray[1]=tmp; MaxHeap(DataArray,1,i-1); } } 调用：
for(int i=1; i<=n; i++) //注意是从1开始 cin>>a[i]; HeapSort(a,n); for(int i=1; i<=n; i++)cout<<a[i]<<" ";
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
