实训一-算法实训报告

《实训一-算法实训报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实训一算法PK赛实训完成时间201&06.10地点11-303实训成绩实训目的通过木次实训内容，帮助学牛理解算法在程序开发中的核心作用，掌握描述算法的方法。实训课时安排6课时实训内容自选一种排序算法，实现将N个杂乱无章的整数按照从小到大的顺序进行排列并输出。算法原理*堆排序堆实际上是一棵完全二叉树，其任佢1一非叶节点满足性质:Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]^Key[i]>=Key[2i+1]&&key>=key[2i+2]即任1可一非叶节点的关键字不大于或者不

2、小于其左右孩子节点的关键字。堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+l]&&key>=key[2i+2]称为大顶堆，满足Key[i]<=key[2i+1]&&Key[i]<=key[2i+2®为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的。算法设计1）初始化堆:将R[l..n]构造为堆；2）将当前无序区的堆顶元素R[l]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。程序清单SincludeRi

3、nclude并include林includevoidlleapAdjust(intarr[],inti.intlength)(intChild;inttemp;for(;2*i+Iarr[Child])卄ChiId;if(arr[i]

4、Child]=temp：}elsebreak;}}voidHeapSort(intarr[],intlength){inti:for(i=length/2-1;i>=0;—i)HeapAdjust(arr,i,length);ford=length-1;i>0：--i)(arr[i]=arr[0]'arr[i]:arr[0]=arr[0]arr[i];arr[i]=arr[0]*arr[i];HeapAdjust(arr,0,i):1}intmainO(FILE*fp;intz=0,j,n.nurns

5、[100000];clock_tstart,end;doublet:fp=fopen(*t.txt*,"r");if(fp=NULL)printff错误.无法打开文件j;return1:}else{while(!feof(fp)){if(fscemf(fp,"%(r,&n)〉O){nums[z]=n;z++：}}}fclose(fp);start=clock0;HoapSort(nums,sizoof(nums)/sizeof(int});end=clock();printf(”排序后的数据是:

6、十)；t=(double)(end-start)/CL(K'KS_F,ER_SEC;for(j=0;j

7、6749976759977199977269977349977469977559977599977619977809977979978259978339978339978359978399978619978639978659978709978849978859979049979059979209979249979419979469979609979649979769979889980179980259980269980289980289980329980419980779981079981089981

8、18998129998140998186998192998202998203998213998243998253998258998265998266998294998299998312998333998339998354998361998373998374998388998407998413998415998429998434998456998459998462998474998485998489998524998534998537998541”9854