快速排序实验报告..docx

南京邮电大学通达学院实验报告实验名称： 快速排序算法 课程名称：微型计算机原理与接口技术姓名 班级学号： 钱煜中 142501 实验时间： 2016.12.2 快速排序原理实验原理：快速排序算法quick sort主要是利用分治递归的思想进行排序的方法。它的原理是首先从待排序的原始序列a[p,…,r]中选取一个元素a[q]作为分界点（pivot），然后将序列分为两个子序列，左边子序列a[p,…,q-1]元素的值都小于分界点m，右边子序列a[q+1,…,r]元素值都大于分界点的值，此时得到的序列命名为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]处的元素作为分界点（pivot）的值。具体第一次分区过程如下：因此，第一次分区，以69为分界点，结果为:a’= [14, 58, 22, 48, 13, 38, 45, 69, 93, 81, 79, 72]。实验代码#include stdio.hint fast_sort(int *a,int i,int j,int *p,int **b){int k,temp,f,g;g=*p;g=(12*g)-12;//intf(成功进入快速排序 g=%d\n,g);k=i;i++;for(;ij;){for(;a[j]a[k]ij;){j--;}for(;a[i]a[k]ij;){i++;}//intf(i=%d\n,i);if(i==j)break;if(ij);{temp=a[i];a[i]=a[j];a[j]=temp;}}if(a[k]a[j]){temp=a[k];a[k]=a[j];a[j]=temp;}//r(f=0;f12;f++)////intf(%3d,a[f]);////printf(排序成功 \n);for(f=0;f12;f++){*(b+g+f)=a[f];}return j;}void digui(int *a,int i,int j,int *p,int **b,int *z){int k;if(ij){//intf(成功进入递归 p=%d\n,*p);*p=*p+1;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)*z=*p;//printf(z=%d\np=%d,*z,*p);*p=*p-1;}}void main(){int a[]={38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72};int b[10][12];int y=0,k,x=0,z=0;printf( 初始序列为 );for(k=0;k12;k++){printf(%3d,a[k] );}printf(\n);digui(a,0,11,x,b,z);for(y=1;yz+1;y++){printf(第%2d次后的数组为,y);for(k=0;k12;k++)printf(%3d,b[y-1][k]);printf(\n);}}实验数据（给出实验结果） 对序列a = [38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72]38 81 22 48 13 69 93 14 45 58 79 7238 14 22 48 13 69 93 81 45 58 79 7238 14 22 13 48 69 93 81 45 58 79 72进行快速排序，其中，以序列的首元素作为排序的分界点。输出结果要求：输出每一次分区后的结果以及最终排序结果。实验总结（问题、解决方法、心得体会等）这次实验我做了很久，重新编写了算法很多次。最开始我对算法的理解不够深，在递归自调用的时候没有想通上下界其实在递归下一层的时候下一层是知道上一层的上下界的，只要排序算法里返还一个最好作为比较值的位置就可以了。一开始排序算法写完就把每次数输出出来，知道后来和同学讨论正确答案是排序了多少次，才想想到我是把每个区排完后的情况，而其实我想输出的是每次排序后数组情况。可是一开始进入的就是左半区的左半区的左半区。。。反正一次是无法输出全部的，因为右半区还没有算。思考了很久，