堆排序算法实现

1.堆排序. 平均复杂度，最坏复杂度都是nlogn

#include <iostream>
using namespace std;

//获得父结点,从0开始
#define get_Parent(i)    ( (i+1) >> 1 -1)     
//获得左孩子节点 
#define get_LeftChild(i) ( (i+1) << 1 -1)
//获得右孩子节点
#define get_RightChild(i) ( (i+1) <<1  )

int  DATALEN  = 10 ;//定义待排序的数据长度


//保持堆的性质
//A表示记录数据的数组，i表示坐标为i的结点
void keep_MaxHeap( int* A , int i )
{
	int l = get_LeftChild(i); //获得左右孩子
	int r = get_RightChild(i);
     
	//比较根节点与孩子节点的大小
    int largest = i; //保存最大值
	if ( l < DATALEN && A[l] > A[i] ) //左孩子
	{
        largest = l;  
	}
	else
		largest = i;
 
	if ( r < DATALEN && A[r] > A[largest] ) //右孩子
	{
        largest = r;  
	}

	if ( largest != i) //如果有改变，则会影响整个子树的结构，应该递归调整
	{
		//先互换
		int temp = A[i];
		A[i] = A[largest];
		A[largest] = temp;
	    keep_MaxHeap(A,largest);//调整以largest为根的子树
	}
   return ;
}

//建立最大堆
//以 DATALEN/2 到 根部不断跟新
void build_MaxHeap(int* A)
{

	for(int i = (DATALEN/2 - 1); i>=0 ; --i )
		keep_MaxHeap(A,i); //维护最大堆
	return ;
}

//堆排序
//方法就是，先建立一个最大堆
//然后将头结点元素与，最后一个一个节点互换
//直到倒数第二个
void heap_Sort(int* A)
{
	DATALEN = 10; //在这儿可以更新数组长度，默认为10
	
	//先建一个最大堆
	build_MaxHeap(A);

	//不断缩小数组大小，建立最大堆
	for ( int i=DATALEN-1; i>=1; --i )
	{
		//交换最大值与数组最后一个数字
		int temp = A[0];
		A[0] = A[DATALEN-1];
		A[DATALEN-1] = temp;
		
		DATALEN-- ; //数组大小又小了一个，因为已经又找到一个最大值放到了后面
		keep_MaxHeap(A,0);
	}

}
int main(void)
{
	int A[10] = {3,4,2,5,6,2,8,7,9,10};
	heap_Sort(A);
	cout<<A[0]<<endl;
	return 0;
}