堆排序

#include <bits/stdc++.h>
using namespace std;
void swap(int &a,int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
void max_heap(int *arr,int start,int end)
{
	int father = start;
	int child = 2*father+1;
	while(child <= end)
	{
		if( (child+1<=end)&&*(arr+child) < *(arr+child+1) )//选出孩子中较大的 
		{
			child++;
		}
		if( *(arr+father) > *(arr+child))//如果father大于孩子返回 
		{
			return ;
		}else//否则交换 
		{
			swap( *(arr+father), *(arr+child) );
			father = child;
			child = child*2 + 1;
		}
	}
}
void sort_heap(int *arr,int len)
{
	//从最后一个父节点构造 
	for(int i = len/2 -1;i>=0;i--)
	{
		max_heap(arr,i,len - 1);//开始构造从下往上
	}
	for(int i=len - 1; i >0 ;i--)//最后到i = 1 说明 只剩下一个元素arr[0]排序完成
	{
		swap( *(arr) , *(arr+i) );//i是要交换的元素 1~i-1是无序需要排序的
		max_heap(arr, 0, i-1);//重新构造从上往下
	}
}
int main()
{
	int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
	int len = sizeof(arr)/sizeof(*arr);
	sort_heap(arr,len);
	for(int i=0;i<len;i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
	
}