快速排序实验报告

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

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

2、应该处于其排好序后的正确位置。然后利用递归的思想，对左右两个子序列a[p，…，q-1]和a[q+l，…，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]处的元素作为分界点(pivot)的值。具体第一次分

3、区过程如下：left献十1

4、1right

5、38

6、81221369

7、冋问问587972ttIohi-hi礞一M

8、69

9、81*

10、22

11、48

12、13l38M卜

13、45!(58J79*[72*]伞Io-•Io一.Io^lohi[69]5822*[48*13*38.93*14

14、45*817972今hilo•lo

15、69]5822

16、48

17、13

18、38

19、45

20、j14“l

21、93*

22、8179

23、

24、72

25、T今hi

26、1458224813384569

27、l93l817972因此，第一次分区，以69为分界点，结果为：a,=[14，58，22，48，1

28、3，38，45，69,93，81，79,72]。二、实验代码#includeintfastsort(int^a,inti,intj,int氺p,int氺氺b){intk,temp,f,g;g=*P;g=(12*g)-12;//intf("成功进入快速排序g=%dg);k:i;for(;ia[k]&&i

29、p=a[i];a[i]=a[j];a[j]=temp;}}if(a[k]>a[j]){temp=a[k];a[k]=a[j];a[j]=tcmp;}//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本a,inti,intj,int氺p,int氺氺b,int氺z){intk;{//intf(〃成功进入递归p=%d〃,*p);氺p二氺p+1

30、;k=fast_sort(a,i,j,p,b);digui(a,i,k-1,p,b,z);digui(a,k+1,j,p,b,z);if(*p>*z)氺氺p;//printf("z=%dp=%d",*z,*p);氺p=*p_l;}}voidmain(){inta[]={38,81,22,48,13,69,93,14,45,58,79,72};intb[10][12];inty=0,k,x=0,z=0;printf(〃初始序列为〃)；for(k=0;k<12;k++)}printf("");digui(a,

31、0,11,&x,b,&z);for(y=l;y

32、的分界点。输出结果要求：输出每一次分区后的结果以及最终排序结果。四、实验总结（问题、解决方法、心得体会等）这次实验我做了很久，重新编写了算法很多次。最开始我对算法的理解不够深，在递归自调用的时候没有想通上下界其实在递归下一层的时候下一层是知道上一层的上下界的，只要排序算法里返还一个最好作为比较值的位置就可以了。一开始排序算法写完就把每次数输出出来，知道后来和同学讨论正确答