学步园

堆排序：包括 建立堆，堆调整

堆排序：不稳定算法

时间复杂度：O(nlogn) [最好，平均，最坏] ; 空间复杂度O(1)

//=======heap sort========最大堆=====================================
template <typename T>
void heap_max_adjust(T *A,int first,int size){
	int i=first;
	int j=2*first+1; //child node
	T temp=A[first];
	while(j<size){
		if(j+1<size && A[j+1]>A[j])
			j++;
		if(A[j]<=temp)
			break;
		A[i]=A[j];
		i=j;
		j=2*i+1;
	}
	A[i]=temp;
}
template <typename T>
void heap_build(T *A,int size){
	for(int i=size/2-1;i>=0;i--)
		heap_max_adjust(A,i,size);
}
template <typename T>
void heap_sort(T *A,int size){
	T temp;
	heap_build(A,size);// build heap
	for(int i=size-1;i>0;i--){
		temp=A[i];
		A[i]=A[0];
		A[0]=temp;
		heap_max_adjust(A,0,i);
	}
}