首页 > 代码库 > 堆排序(最大堆)
堆排序(最大堆)
#include "iostream.h" using namespace std; //因为i从0开始 #define LeftChild(i) (2*(i)+1) //i-N范围内,创建最大堆 void maxHeap(int A[], int i, int N){ int tmp; int child; for(tmp=A[i];LeftChild(i)<N;i=child){ child = LeftChild(i); if(child!=N-1&&A[child+1]>A[child]){ child++; } if(tmp<A[child]){ A[i]=A[child]; }else break; } A[i]=tmp; } void HeapSort(int A[], int N){ //因为2*i不超过N,所以i从N/2开始 for(int i=N/2;i>=0;i--){ maxHeap(A,i,N); } for(int i=N-1;i>0;i--){ //A[0]是最大堆的最大值,通过交换,把堆的最大值置于队尾 swap(A[0],A[i]); //重建最大堆 maxHeap(A,0,i); } } int main(int argc, char *argv[]) { int N; cin>>N; int A[100]; for(int i=0;i<N;i++){ cin>>A[i]; } HeapSort(A,N); for(int i=0;i<N;i++){ cout<<A[i]<<" "; } cout<<endl; return 0; }
堆排序(最大堆)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。