实验五(快速、堆、基数)排序算法的设计.doc

实验五 （快速、堆、基数）排序算法的设计一、 实验目的和要求实验目的：1.深刻理解排序的定义和各种排序方法的特点，并能灵活运用。2.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。3.了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。实验要求：要求彻底弄懂排序的物理存储结构，并通过此试验为以后的现实使用打下基础。二、 实验内容和原理（1）实验内容： 设计快速排序，堆排序和基数排序的算法。（2）实验原理： 快速排序：在待排序的n个数据中，任取一个数据为基准，经过一次排序后以基准数据把全部数据分为两部分，所有数值比基准数小的都排在其前面，比它大的都排在其后，然后对这两部分分别重复这样的过程，直到全部到为为止。堆排序：对待排序的n个数据，依它们的值大小按堆的定义排成一个序列，从而输出堆顶的最小值数据（按最小值跟堆排序），然后对剩余的数据再次建堆，便得到次小的，如此反复进行输出和建堆，直到全部排成有序列。基数排序：LSD法：先按最低关键字位k1对待排序数据中的n个值进行排序，按k1值把待排序文件中的n个记录分配到具有不同k1值的若干个堆，然后按k1值从小到大的次序收集在一起，下次再按高一位关键子位k2的值进行分配和收集，如此不断地按更高一位关键字位进行分配和收集，直到用kn分配和收集之后，整个数据按多关键字位有序。堆排序：堆排序分为建堆和堆调整，初始建堆时将与此序列对应的一维数组看成是一棵完全二叉树，从完全二叉树的最后一个结点K(i)（i等于n/2向下取整）开始，通过调整逐步使以K(i)到K(1)为根的子树满足堆的定义，直到以K(1)为根的树满足堆定义时初始堆建成。堆调整在出堆顶记录之后，用堆中的最后一个记录替代原堆顶记录。由于除根节点K(i)之外的所有子树仍具有堆的性质，故只需对根结点自上而下调整即可。三、 实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统 （2）Turbo C 3.0四、 算法描述及实验步骤1) 快速排序设两个指示器变量i和j，分别指向待排序区间的第一个记录和最后一个记录;先将第一个记录移到暂存变量temp中，然后j从区间的最后一个记录起向前扫描，直到找到满足Rjtemp.key的记录时，将Rj移入Ri中; 就这样j自j-1从后向前扫描一次移入一个Rj于Ri中，i自i+1从前向后扫描一次移入一个Ri于Rj中，反复交替地扫描和移动记录；直到i=j时把temp移入Ri中（区间中第一个记录应在位置），它把整个待排序区间分割成为两个区间的一个分割排序算法；对于待排序文件R利用一个分割区间排序算法时，令s=1和t=n即可完成第一趟排序；由此得到的两个更小的区间R1，i-1和Ri+1,，n,继续利用算法dividesreasort分割为更小的4个区间；如此一直进行下去，直到都分割为只有一个记录时排序结束。2) 堆排序 堆调整是从根结点向下的一个筛选过程；而建初始堆是从最后一个分枝结点开始到根结点结束的多次向下的筛选过程；3） 基数排序 第1趟分配按最低关键字位进行，改变记录结点的指针值将文件中的所有记录分配到10个队列中；第2趟的分配和收集以及第3趟的分配和收集是分别针对关键字中的十数和百位数进行的，其分配和收集过程与个位数时相同。五、 调试过程（一）快速排序1)2)3)（2） 堆排序1)2)六、 实验结果（1） 快速排序（2） 堆排序（3） 基数排序七、 总结 从懵懂到懂得，这是通过调试过程所得到的收获；再次回顾了之前所学的单链表结构的建立，堆的建立。从中体会快速排序、堆排序、基数排序算法的思想，如何优化算法是将来需要进一步改善的地方。附录：代码快速排序#includestdio.h#define Maxsize 100#define m 10void quicksort(int R,int n) int i,j,low,high,temp,top=-1; struct node int low,high; stMaxsize; top+; sttop.low=0;sttop.high=n-1; while(top-1) low=sttop.low;high=sttop.high; top-; i=low;j=high; if(lowhigh) temp=Rlow; while(i!=j) while(itemp)j-; if(ij)Ri=Rj;i+; while(ij&Ritemp)i+; if(ij)Rj=Ri;j-; Ri=temp; top+;sttop.low=low;sttop.high=i-1; top+;sttop.low=i+1;sttop.high=high; int main() int i,n;int Rm;printf(please input the number of the data you want to sort:);scanf(%d,&n);printf(input the numbers :);for (i=0;in;i+) scanf(%d,&Ri); quicksort(R,n); for(i=0;in;i+) printf(%d ,Ri); printf(n);堆排序#includestdio.hvoid heapadjust(int R,int s,int t)/对R进行筛选的堆调整算法，除Rs外其他位置都满足最小值根堆定义int i,j;/定义局部变量i=Rs;/i初始化Rsj=2*s+1;/j初始化为2*s+1while(jt)/逐层向下筛选if(jt-1)&(RjRj+1)j+;if(i=0;i-)heapadjust(R,i,n);/调用筛选算法建立初始堆for(i=n-1;i=1;i-)/n-1次输出堆顶记录并调整堆j=R0;/堆顶记录与当前堆中最后一个记录交换R0=Ri;Ri=j;heapadjust(R,0,i);/调用筛选算法重建堆void main()int i,R4;printf(input the numbers :);for(i=0;i4;i+)scanf(%d,&Ri);heapsort(R,4);for(i=0;i=1;i-)/控制3趟分配和收集for(j=0;jrd;j+)/队列头指针初始化为null fj=-1; ej=-1;while(p!=-1)/控制一趟中各记录结点的分配k=Rp.keyi;/p结点的第i关键字位的值送k中if(fk=-1)fk=p;elseRek.next=p;/否则插入队尾ek=p;/修改队尾指针向刚插入的结点p=Rp.next;/p指向下一个记录结点，为后续分配做准备j=0;/一趟分配完成后，为后续分配做准备while(fj=-1)j+;/找第一个非空队列p=fj;/第一个非空队列队头指针送pt=ej;/第一个非空队列队头指针送twhile(jrd-1)/控制一趟的收集j+;/j指向下一个队列if(fj!=-1)/若第j个队列不空Rt.next=fj;/队头接入收集链尾t=ej;/t指向队尾，即收集链尾Rt.next=-1;/本趟收集完毕，将链尾指针域置为nullreturn p;/d趟分配和收集完成后返回指向排序结果链第一个结点的指针值pmain()int