算法与数据结构实验5

《算法与数据结构实验5》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、福建农林大学实验报告系(教研室)：计算机专业:年级：实验课程：姓名：学号：实验室号：计算机号：实验时间：指导教师签字：成绩：实验五(快速、堆、基数)排序算法的设计实验目的和要求实验目的：1.深刻理解排序的定义和各种排序方法的特点，并能灵活运用。2.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。3.了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。实验要求：要求彻底弄懂排序的物理存储结构，并通过此试验为以后的现实使用打下基础。二、实验内容和原理(1)实验内容：设计快速排序，堆排序和基数排序的算法。(2)实验原理：快速排序：在待排

2、序的n个数据中，任取一个数据为基准，经过一次排序后以基准数据把全部数据分为两部分，所有数值比基准数小的都排在其前面，比它大的都排在其后，然后对这两部分分别重复这样的过程，直到全部到为为止。堆排序：对待排序的n个数据，依它们的值大小按堆的定义排成一个序列，从而输出堆顶的最小值数据(按最小值跟堆排序)，然后对剩余的数据再次建堆，便得到次小的，如此反复进行输出和建堆，直到全部排成有序列。基数排序：LSD法：先按最低关键字位kl对待排序数据中的n个值进行排序，按kl值把待排序文件中的n个记录分配到具有不同kl值的若干个堆，然后按kl值从小到大的次序收集在一起，下次再按

3、高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，直到用kn分配和收集之后，整个数据按多关键字位有序。三、实验环境硕件：(1)学生用微机(2)多媒体教室或远程教学(3)局域网环境软件：(1)WindowsXP中文操作系统(2)TurboC3.0四、算法描述及实验步骤1、算法描述快速排序算法描述：用两个变量i,j分別指向待排序列的笫一个记录和最后一个记录；先将第一个记录保存到R[0]屮，然后j从最后一个记录起向前扫描，直到找到R[j].key

4、].key>R[O].key时R[i]移到R[j]中；就这样j自j+1从后向前扫描一次移入一个R[j]于R[i]中，i自i+1向后扫描一次移入一个R[i]于R[j]中，反复交替地扫描和移到记录;直到i二j时把R[0]给R[i]中，他把整个待排序区间分割为两个更小的序列，再将以上过程，直到区间为大小为1时，排序结束。堆排序算法描述：堆排序分为建堆和堆调整，初始建堆时将与此序列对应的一维数组看成是一棵完全二叉树，从完全二叉树的最后一个结点K(i)(i等于n/2向下取整)开始，通过调整逐步使以K(i)到K(l)为根的子树满足堆的定义，直到以K(1)为根的树满足堆定义

5、时初始堆建成。堆调整在出堆顶记录之后，用堆中的最后一个记录替代原堆顶记录。市于除根节点K(i)之外的所有子树仍具有堆的性质，故只需对根结点自上而下调整即可。基数排序算法描述：可分为分配和收集。引入一个为结构体的辅助数组用于分配吋保存同一关键位的元素。个位数字为低关键字位，十位数字为高关键字位。关键字位值的范围为0—9,qu[i].f与qu[i].r为第i个队列的头指针和尾指针。将不qu[i].f不为空的链表相连，进行收集。直到所有的关键字位都被分配完毕，收集完毕后退出。2、算法流程图快速排序:beginend基数排序:N3、代码(注释)#include"st

6、dio.h"#definemax100#dcfincrd10#defined3typedefstruct/*定义结构体*/{intkey;intke[d+l]；/*elemtypeotheritems;*/intnext;(recordtype;intf[rd],e[rd];intdivideareasort(recordtypeR[],ints,intt)/*对待排序记录区间R[s]到R[t]以R[s]为基准进行一次分割排序,并返回基准记录的最终位置*/{inti,j;_rccordtypctemp;/*定义暂存工作单元*/i=s;j=t;temp=R[s]

7、;/*确定分割基准*/do{while((R[j].key>=temp.key)&&(i

8、

9、

10、Jnts,intl)/*对待排序文件R