堆排序

//若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
//树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
//注意：是从坐标1开始的

//假设完全二叉树的某一个节点i,它的左子树，右子树已经是堆，接下来需要将r[2i].key与r[2i+1].key之中的最大者与
//r[i].key比较，若r[i].key较小则将其与最大孩子的关键字交换，这有可能破坏下一级的堆，于是继续采用上述方法构造下一级的
//堆，知道完全二叉树中的节点i构成堆为止。对于任意一颗完全二叉树，i取[n/2]~1,反复利用上述方法建堆。大者“上浮”，小者“下沉”。

#include <iostream>
using namespace std;
#define Type int

void sift(Type r[],int low,int high)
{
	int i=low,j=2*i;
	Type tmp=r[i];
	while(j<=high)
	{
		if (j<high && r[j] < r[j+1])
			++j;///////////找到较大的孩子
		if (tmp < r[j])//若较大的孩子大于父节点的，就交换，交换了就得处理下一级堆
		{
			r[i]=r[j];
			i=j;
			j=2*i;
		}
		else break;//没交换，不用交换不用处理下一级堆
	}
	r[i]=tmp;
}
void heapsort(Type r[],int n)
{
	int i;
	Type tmp;
	for ( i = n/2; i >= 1; --i)//循环建立初始堆
      sift(r,i,n);

  for ( i = n; i >= 2; --i)
  {
  	tmp=r[1];
  	r[1]=r[i];
  	r[i]=tmp;
  	sift(r,1,i-1);//每一趟排序的基本操作：将当前无序区的堆顶记录R[1]
  	             //和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。
  }
}

int main(int argc, char const *argv[])
{
	Type r[9]={0,51,54,55,15,15,1,787,5};
	heapsort(r,8);
	for (int i = 1; i < 9; ++i)
	{
		cout<<r[i]<<" ";
	}
	return 0;
}

堆排序,布布扣,bubuko.com

堆排序

原文：http://blog.csdn.net/h1023417614/article/details/20847331