首页 > 代码库 > 让算法会说话之堆排序
让算法会说话之堆排序
转载请注明出处: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 著
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。