排序有很多种，堆排序的耗时是nlogn的现在学习一下。

一开始我尝试运用链表来建立一个堆，但是发现，对于一个堆来说，我们正常的输入都是按照层序输入的，但是层序建堆感觉非常不好建如果用链表的话，还要在输入的时候先进行一次先序或中序或后序变化才行，这增加了许多麻烦，因此放弃链表建堆了，改用数组建堆，就可以实现层序输入了；

对于一个数组，从0开始是他的根节点，那么他的子节点就分别是2*1-1和2*1，因此，对于每个父节点n他的子节点就分别是2*（n+1）-1和2*（n+1）。同理，一个子节点n的父节点就是（n-1）/2；

这样看下去，每个节点都有与之对应的下标，然后在进行堆排序；

1.输入一个无序数组；

2.排成一个大顶堆（根节点大于等于任意子节点）或者小顶堆（根节点小于等于任意子节点）；

3.进行排序；

#include<stdio.h>    
#include<string.h>    
#include<math.h>    
    
//#include<map>     
#include<set>  
#include<deque>    
#include<queue>    
#include<stack>    
#include<string>    
#include<iostream>    
#include<algorithm>    
using namespace std;    
    
#define ll long long    
#define da    0x3f3f3f3f    
#define clean(a,b) memset(a,b,sizeof(a))// 水印 

/*5  4 6 8 5 9

		4
	6	  	8
  5  9
  
  9  9 5 1 3 2 6 4 8 7
  9  1 2 3 4 5 6 7 8 9 
*/

void swap(int *shuzu,int i,int j)//交换函数 i，j； 
{
	int temp=shuzu[i];
	shuzu[i]=shuzu[j];
	shuzu[j]=temp;
}

void adjust_heap(int *shuzu,int i,int n)
{
	int temp=shuzu[i];//取该节点的值 
	int k,j;
	for(k=i*2+1;k<n;k=k*2+1)//根节点是 0，那么子节点分别是（n+1）*2-1，（n+1）*2； 
	{//找第一个子节点，该子节点找该子节点的 第一个子节点 
		if(k+1<n&&shuzu[k]<shuzu[k+1])//该节点有右节点&&右节点>左节点 
			++k;//选取右节点 
		if(shuzu[k]>temp)//最大的节点是否大于父节点 
		{
			shuzu[i]=shuzu[k];//父节点取最大值 
			i=k;//以该点为父节点再次调整 
		}
		else
			break;//符合大顶堆结束 
	}
	shuzu[i]=temp;//最后找到的节点放入初始值 
}

void sort_heap(int *shuzu,int n)
{
	int i,j; 
	for(i=n/2-1;i>=0;--i)//从最后一个父节点开始 建立一个大顶堆 
		adjust_heap(shuzu,i,n);//调整该节点 
	for(j=n-1;j>0;--j)//每次交换堆顶的最大值至堆尾 ,然后该点超脱（不再参与排序） 
	{
		swap(shuzu,0,j);
		adjust_heap(shuzu,0,j);//调整大顶堆符合要求 大数放置后面 
	}
}




int main()
{
	int n,shuzu[110];
	cin>>n;
	int i,j;
	for(i=0;i<n;++i)
		cin>>shuzu[i];
	
	sort_heap(shuzu,n);//从小到大排序 
	for(i=0;i<n;++i)
		cout<<shuzu[i]<<" ";
}