堆排序code
#include<bits/stdc++.h>
using namespace std;
#define maxn 501
int arr[maxn];
void swap(int i,int j){
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
//向上调整函数
void heapinsert(int x){
if(x==0) return;
int i=(x-1)/2; //父节点
while(1){
if(i<0||arr[i]>=arr[x]) break;
else{
swap(x,i);
}
x=i;
i=(i-1)/2;
}
}
//向下调整函数
void heapify(int pl,int size){
int l=pl*2+1;
if(l>=size){
return;
}
while(l<size){
int best=(l+1<size)?(arr[l]>arr[l+1]?l:l+1):l;
if(arr[best]>arr[pl]){
swap(best,pl);
}
else{
break;
}
pl=best;
l=pl*2+1;
}
}
//从顶到底建堆排序
void heapsort1(int n){
for(int i=0;i<n;i++){
heapinsert(i);
}
int size=n;
while(size>1){
size--;
swap(0,size);
heapify(0,size);
}
}
//从底到顶建堆排序
void heapsort2(int n){
for(int i=n-1;i>=0;i--){
heapify(i,n);
}
int size=n;
while(size>1){
size--;
swap(0,size);
heapify(0,size);
}
}
void print(int arr[],int n){
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
puts("");
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
//heapsort1(n);
//print(arr,n);
heapsort2(n);
print(arr,n);
return 0;
}