堆排序的设计与实现

堆排序的设计与实现

ID:8463052

大小:226.50 KB

页数:28页

时间:2018-03-28

堆排序的设计与实现_第1页
堆排序的设计与实现_第2页
堆排序的设计与实现_第3页
堆排序的设计与实现_第4页
堆排序的设计与实现_第5页
资源描述:

《堆排序的设计与实现》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、2.概要设计2.1数据结构设计用一维数组a[]存储。数组a[1000],a[0]=-1;2.2算法设计//直接选择排序voidchosemin(inta[],intn,intz){intb=a[z];for(inti=z;i

2、idchosemax(inta[],intn,intz){intb=a[z];for(inti=z;i=a[i+1]){continue;}elseb=a[i+1];}for(intx=z;x<=n;x++){if(a[x]==b){break;}}-27-intt=a[z];a[z]=a[x];a[x]=t;printf("选择数组a中剩下的元素中最大的一个:t");printf("%d",a[z]);}//堆排序voidshift(inta[],inti,intn){intt=a[i],j=i+i;while(j<=n){if

3、(ja[j+1])j++;if(t>a[j]){a[j/2]=a[j];a[j]=t;j=j*2;}elsebreak;}}-27-voidheapsort(inta[],intn){intb=0;inti,temp;for(i=n;i>0;i--){temp=a[i];a

4、[i]=a[1];a[1]=temp;shift(a,1,i-1);b=b+1;printf("输出第%d个元素:%d",b,a[i]);if(i!=1)printf("开始构建剩下元素的大顶堆");}getchar();getchar();}-27-voidheapsortSmall(inta[],intn){intb=0;inti,temp;for(i=n;i>0;i--){temp=a[i];a[i]=a[1];a[1]=temp;shiftSmall(a,1,i-1);b=b+1;printf("输出第%d个元素:%d",b,a[i]);if

5、(i!=1)printf("开始构建剩下元素的小顶堆");}getchar();getchar();}-27-2.3ADT描述ADTArray{数据对象:ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…jn

6、n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2…jn∈ElemSet}数据关系:R={R1,R2,R3,…,Rn}Ri={

7、0<=jk<=bk-1,1<=k<=n且k≠i,0<=ji<=bi-2,aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…

8、,n}基本操作:voidshift(inta[],intI,intn)初始条件:数组a已存在,i为n/2,n为数组的长度操作结果:把数组a中n个元素构造成为一个大顶堆。voidshiftSmall(inta[],inti,intn)初始条件:数组a已存在,i为n/2,n为数组的长度操作结果:把数组a中n个元素构造成为一个小顶堆。voidheapsort(inta[],intn)初始条件:数组a已存在,n为数组长度。操作结果:把数组a中n个元素循环构建大顶堆,并输出堆顶元素。-27-voidheapsortSmall(inta[],intn)初始条件:数组a已存在

9、,n为数组长度。操作结果:把数组a中n个元素循环构建小顶堆,并输出堆顶元素。chosemin(inta[],intz,intn)初始条件:数组a已存在,z为数组剩下的元素,n为数组长度。操作结果:数组a从第z个元素中开始找最小的一个并与a[z]换位并并输出a[z]。chosemax(inta[],intz,intn)初始条件:数组a已存在,z为数组剩下的元素,n为数组长度。操作结果:数组a从第z个元素中开始找最大的一个并与a[z]换位并输出a[z]。}2.4功能模块分析这个程序实现的是一个堆排序和一个直接选择排序的功能。它分为3个模块:1.输入数据元素。2.把数

10、组元素通过直接选择排序的

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。