rC程序设计基础实验指导

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,?数据结构?实验指导,实验,8,内排序,实验目的,1,、掌握线性表的排序方法。,2,、并分析时间复杂度。,实验,8,内排序,实验内容,问题描述：将快速排序算法写成完整的程序上机通过，并统计递归深度。,输入：待排序记录个数,n,，各待排序记录值。,输出：,n,个记录由小到大排列的结果。,存储结构：待排序记录顺序存储。,实验,8,内排序,实验内容,算法的根本思想：快速排序算法每次任取一个记录的关键字为标准，将其余记录分为两组，将所有关键字小于或等于标准的记录都放在它的位置之前，将所有关键字大于标准的记录都放在它的位置之后。对这两组再进行快速排序，直到完全有序。每递归1次，递归深度加1。,实验,8,内排序,实验内容,参考源程序：,#include,typedef int node;,node afile20;,node x;,int d,dl,n;,int l,r,i,j;,void q(int l,int r),int p;,d+;,if(dld),dl=d;,printf(dl=%d ,dl);,printf(d=%dn,d);,实验,8,内排序,实验内容,if(lx)&(ji),j-;,if(ij),afilei+=afilej;,while(afileii),i+;,if(ij),afilej-=afilei;,实验,8,内排序,实验内容,afilei=x;,for(p=1;p=n;p+),printf(%d,afilep);,printf(n);,q(l,i-1);,q(i+1,r);,d-;,printf(*%d*n,d);,main(),int p;,printf(nPlease input n:n);,scanf(%d,printf(Please input a string:);,for(p=1;p=n;p+),实验,8,内排序,实验内容,scanf(%d,d=0;dl=0;,l=1;r=n;,q(l,r);,for(p=1;p=n;p+),printf(%d,afilep);,printf(n);,printf(dl=%dn,dl);,