首页 > 代码库 > 让算法会说话之堆排序

让算法会说话之堆排序

转载请注明出处:http://blog.csdn.net/ruoyunliufeng/article/details/26364047     


       堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质即子结点的键值或索引总是小于(或者大于)它的父节点

一.堆的删除

        虽然在这里我默认读者对“”是有所了解的,但是这里我仍然要讲一下堆的删除,因为这直接影响你对下面堆排序的理解。

        这里以删除最小元为例讲解,当然下面的堆排序时删除最大元,但这并不妨碍我们对“堆的删除”的理解。

核心思想:将最小元删掉,其他的元根据堆的性质排好。

二.堆排序算法

/***************************************************************
*版权所有 (C)2014,公司名称。
*
*文件名称:堆排序法
*内容摘要:无
*其它说明:无
*当前版本:V1.0
*作   者:若云流风
*完成日期:2014.5.20
***************************************************************/
#include <stdio.h>

#define N  7
#define LeftChild(i)   (2*(i)+1)              //i节点的左儿子节点

void disp(void);

int a[N]={5,0,7,1,9,11,12};


/*下滤函数(目的:根据堆的性质将堆排好)*/
void PerDown( int a[], int i ,int M)
{
	int Child,tmp;

	for( tmp=a[i]; LeftChild(i)<M; i=Child )       //将根节点赋值tmp,判断根的左儿子是否存在
	{
		Child=LeftChild(i);
		if( Child !=M-1  &&  a[Child+1]>a[Child] ) //判断节点儿子是否是两个(M为奇数时),如果是两个再判断哪个更大
			Child++;
		if( tmp<a[Child] )                         //将节点的儿子与节点比较,如果儿子大则交换位置
			a[i]=a[Child];
		else
			break;                                 //否则退出循环
	}
	a[i] =tmp;                                     //如果节点的儿子大实际执行的是a[Child]=a[i];否则a[i]的值没有变化
}

/*排序函数*/
void HeapSort(void)  
{  
	int i,temp;

	for(i=N/2;i>=0;i--)  /*BuildHeap*/
		PerDown(a,i,N);
	disp();              //调试打印1  (将无序数组变成堆后的数组)

	for(i=N-1;i>0;i--)   /*DeleteMax*/
	{
		temp = a[0];     /*删掉最大元:将他移到数组末尾*/
		a[0] = a[i];
        a[i] = temp;
		disp();          //调试打印2  (将最大元素放到末尾的数组)
		PerDown(a,0,i);  /*每次下滤上次最大的元(现在在数组末)都不再参与*/
		disp();          //调试打印3  (下滤后的新数组)

	}
	disp();              //调试打印4  (最终的数组)
}  

/*输出函数*/
void disp(void)
{
     int i;

     printf("\n排序结果: \n");
	 for(i=0;i<N;i++)
	 {
		printf("%d", a[i]);
		printf("  ");
	 }
	
}

int main(void)
{
	HeapSort();
    //disp();
	return 0;

}


三.算法会说话

    1.结果输出


    2.结果分析

好吧我承认也许只看上图也许有些晕,不要紧,接着看我分析。

首先看看如何将数组变成堆:

最终结果就是结果输出中的的“1”。


然后再来看看整个排序的过程:



参考:1.数据结构与算法分析---C语言描述     Mark Allen Weiss 著