堆排序.txt

常见算法

#include<iostream>
using namespace std;
#define N 10
int heapsize=9;                                   //heapsize是一个全局变量，在排序时控制着建堆的范围
void heapify(int B[],int i)                           //保持堆的性质定义
{
    int l,r,largest,key;                           //设置左子节点、右子节点、和其父节点
    l=2*i+1;                              //取左子节点和右子结点   
	r=2*i+2;
	if ((l<=heapsize)&&(B[l]>B[i]))
		largest=l;
	else 
		largest=i;
	
    if((r<=heapsize)&&(B[r]>B[largest]))
		largest=r;
	if (largest!=i)
	{
		key=B[i];
		B[i]=B[largest];
		B[largest]=key;
		heapify(B,largest);
	}
}
	void build_heap(int a[])
	{
		int i;
		int length=N-1;//sizeof(a)/sizeof(a[0]);
		for (i=(length-1)/2;i>=0;i--)                         //建堆过程
		{
			heapify(a,i);
		}
	}
main()                                       //进入排序过程
{
	int i,key;
	int a[N];
	//int heapsize=sizeof(a)/sizeof(a[0])-1;
	cout<<"请输入十个数："<<endl;
	for (i=0;i<10;i++)
	{
		cin>>a[i];
	}

    build_heap(a);                            //建堆
	cout<<"建好的堆是："<<endl;
	for (i=0;i<N;i++)                         //输出建好的堆
	{
		cout<<a[i]<<"  ";
	}
    cout<<endl;

              
	while (heapsize>0)                        //排序过程
	{
         key=a[0];
		 a[0]=a[heapsize];
		 a[heapsize]=key;
		 
		 heapsize--;
         heapify(a,0);
	}
	cout<<"排序后的数组是："<<endl;
	for (i=0;i<N;i++)
	{
		cout<<a[i]<<"  ";
	}
	cout<<endl;
	return 0;
}

//排序编程思想：把堆的根和最后一个元素调换，然后去掉最后一个元素，剩余的元素再建堆，再调换再建堆如此循环一直到最后
//一个元素为止。