快速排序实验报告材料

《快速排序实验报告材料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文档南京邮电大学通达学院实验报告实验名称：快速排序算法课程名称：微型计算机原理与接口技术文案大全实用标准文档姓名班级学号：钱煜中14250114250120实验时间：2016.12.2快速排序原理一、实验原理：快速排序算法quicksort主要是利用分治递归的思想进行排序的方法。它的原理是首先从待排序的原始序列a[p,…,r]中选取一个元素a[q]作为分界点（pivot），然后将序列分为两个子序列，左边子序列a[p,…,q-1]元素的值都小于分界点m，右边子序列a[q+1,…,r]元素值都大于分界点的值，此时得到的序列

2、命名为a’，而a[q]应该处于其排好序后的正确位置。然后利用递归的思想，对左右两个子序列a[p,…,q-1]和a[q+1,…,r]再分别进行排序，直到子序列的长度为1结束，序列有序。其中，选取a中的基准分界点的方式有多种，或者选择序列的首元素a[p]，或者选择序列的尾元素a[r]，或者选择序列中间位置的元素a[(p+r)/2]，或者取这三个元素按照大小排序后的中间值。文案大全实用标准文档例子：a=[38,81,22,48,13,69,93,14,45,58,79,72]，取[(left+right)/2]处的元素作为分界点（p

3、ivot）的值。具体第一次分区过程如下：因此，第一次分区，以69为分界点，结果为:a’=[14,58,22,48,13,38,45,69,93,81,79,72]。二、实验代码#includeintfast_sort(int*a,inti,intj,int*p,int**b)文案大全实用标准文档{intk,temp,f,g;g=*p;g=(12*g)-12;//intf("成功进入快速排序g=%d",g);k=i;i++;for(;ia[k]&&i

4、;a[i]a[j])文案大全实用标准文档{temp=a[k];a[k]=a[j];a[j]=temp;}//r(f=0;f<12;f++)////intf("%3d",a[f]);////printf("排序成功");for(f=0;f<12;f++){*(b+g+f)=a[f];}returnj;}voiddigui(int

5、*a,inti,intj,int*p,int**b,int*z){intk;if(i*z)*z=*p;文案大全实用标准文档//printf("z=%dp=%d",*z,*p);*p=*p-1;}}voidmain(){inta[]={38,81,22,48,13,69,93,14,45,58,79,72};i

6、ntb[10][12];inty=0,k,x=0,z=0;printf("初始序列为");for(k=0;k<12;k++){printf("%3d",a[k]);}printf("");digui(a,0,11,&x,b,&z);for(y=1;y

7、,14,45,58,79,72]388122481369931445587972381422481369938145587972381422134869938145587972进行快速排序，其中，以序列的首元素作为排序的分界点。输出结果要求：输出每一次分区后的结果以及最终排序结果。文案大全实用标准文档二、实验总结（问题、解决方法、心得体会等）文案大全实用标准文档这次实验我做了很久，重新编写了算法很多次。最开始我对算法的理解不够深，在递归自调用的时候没有想通上下界其实在递归下一层的时候下一层是知道上一层的上下界的，只要排序算法里

8、返还一个最好作为比较值的位置就可以了。一开始排序算法写完就把每次数输出出来，知道后来和同学讨论正确答案是排序了多少次，才想想到我是把每个区排完后的情况，而其实我想输出的是每次排序后数组情况。可是一开始进入的就是左半区的左半区的左半区。。。反正一次是无法输出全部的，因为右半区还