堆排序

实现原理：

比如我们现在要进行从小到大的排序，则我们可以先建立最小堆（之前写过最小堆的建立，网址 https://blog.csdn.net/weixin_43570155/article/details/103946065），然后每次删除顶部元素（删除后将最后一个元素插入至根节点）并将顶部元素输出或者放入一个新的数组中，直到堆为空位置。最终输出的或者存放在新数组中的那个数就是已经排序好了的。

时间复杂度

O(NlogN)

代码：

#include<bits/stdc++.h>
using namespace std;
int h[100];
int n;
void swap(int i,int t){
	int temp;
	temp=h[i];
	h[i]=h[t];
	h[t]=temp;
}
void shiftdown(int i){
	int flag=0; //用于标记是否还需要向下调 
	int t=i;//存数字小的下标 
	while(i*2<=n&&flag==0){  //至少存在左子树 
		if(h[i*2]<h[i])    t=i*2;
		if(i*2+1<=n){  //存在右子树 
			if(h[i*2+1]<h[t])   t=i*2+1;
		}
		if(t!=i){   //发现最小的节点编号不是自己，即子节点中存在比父节点小的数 
			swap(i,t);
			i=t;   //更新i点，以便于再次比较下面的点 
		}
		else
		flag=1;   //该点比一下的点都小，不需要向下找了 
	}
}
int deletemin(){
	int t;
	t=h[1];
	h[1]=h[n];  //将堆 的最后一个点赋值到堆顶
	n--;
	shiftdown(1);  //向下调整
	return t;      //返回被删除前的最小值 
}
int main(){
	scanf("%d",&n);
	int k=n;
	for(int i=1;i<=n;i++){
		scanf("%d",&h[i]);
	}
	for(int i=n/2;i>0;i--){   //构建最小堆 
		shiftdown(i);
	}
	for(int i=1;i<=k;i++)    printf("%d ",deletemin());
	
	
	
	
}