首页 > 代码库 > 堆排序

堆排序

先看下堆的概念:堆是一种数据结构,逻辑上是一种完全的二叉树,在存储上是数组对象。

堆分为小顶堆和大顶堆,顾名思义:小顶堆是指顶部的元素是最小的,大顶堆是指顶部的元素师最大的。

这样只要我们能够得到这样的堆,每次将顶部的元素和数列的最后一个元素进行交换,然后再对剩下的元素进行建堆,接着以此类推这样的做法,便可以得到排好的数列了。

根据上面所述,堆排序的关键是:建堆。建堆也分为调堆和建堆过程;

调堆的过程是:比较一个节点和他的子节点的大小,将最小的或者最大的数和父节点交换,交换后的子节点再接着当做父节点做同样的比较,知道不需要交换为止;代码如下:

void _adjust_heap(int *A,int size,int element)
{
	int left=2*element+1;
	int right=left+1;
	int min=0;
	while(left<size)
	{
		min=left;
		if(right<size)
		{
			if(A[min]>A[right]) min=right;
		}
		if(A[element]>A[min]) swap(A[element],A[min]);
		else break;
		element=min;
		left=2*element+1;
		right=left+1;
	}
}</span>

建堆的过程是:对堆的非叶子节点进行调堆,就完成了建堆的过程。

void _build_heap(int *B,int size)
{
	for(int i=size/2-1;i>=0;i--)
	{
		_adjust_heap(B,size,i);
	}
}</span>

排序的过程:对数组进行建堆,每次将第一个元素和最后一个元素交换,然后数组的规模减一,再建堆,直到只剩下一个元素为止。

void _sort(int *A,int size)
{
	int length=size;
	for(;length>=1;length--)
	{
		_build_heap(A,length);
		swap(A[length-1],A[0]);
	}
}</span>

编写程序进行测试:

void main()
{
	int ia[]={0,3,2,6,2,9,2,3,1};
	int size=sizeof(ia)/sizeof(int);
	_sort(ia,size);
	for(int i=0;i<size;i++)
	{
		cout<<ia[i]<<endl;
	}
}</span>
测试结果为:



堆排序