排序算法C语言版堆排序_第1页
排序算法C语言版堆排序_第2页
排序算法C语言版堆排序_第3页
排序算法C语言版堆排序_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、堆排序算法思想简单描述：堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n个元素的序列（h1,h2,.,hn),当且仅当满足（hi=h2i,hi=2i+1）或（hi=h2i,hi=2i+1）(i=1,2,.,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依

2、此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。堆排序是不稳定的。算法时间复杂度O(nlog2n)。算法实现：/*功能：渗透建堆输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始*/void sift(int *x, int n, int s)int t, k, j;t = *(x+s); /*暂存开始元素*/k = s; /*开始元素下标*/j = 2*k + 1; /*右子树元素下标*/while (jn) if (jn-1 & *(x+j) *(x+j+1)/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/ j+; if (t=0; i-) sift(x,n,i); /*初始建堆*/ for (k=n-1; k=1; k-) t = *(x+0); /*堆顶放到最后*/ *(x+0) = *(x+k

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论