快速排序实验报告

1、南京邮电大学通达学院实验报告实验名称：快速排序算法课程名称：微型计算机原理与接口技术姓名班级学号：钱煜中14250114250120实验时间：快速排序原理一、实验原理：快速排序算法 quick sort 主要是利用分治递归的思想进行排序的方法。它的原理是首先从待排序的原始序列ap,r中选取一个元素 aq 作为分界点( pivot )，然后将序列分为两个子序列，左边子序 列ap,q-1元素的值都小于分界点 m ,右边子序列aq+1,r元 素值都大于分界点的值，此时得到的序列命名为a ，而aq应该处于其排好序后的正确位置。 然后利用递归的思想， 对左右两个子序列 ap,q-1和aq+1,r再分别进

2、行排序，直到子序列的长度为 1 结束，序列有序。其中， 选取 a 中的基准分界点的方式有多种， 或者选择序列的首 元素 ap ，或者选择序列的尾元素 ar ，或者选择序列中间位置的元 素 a(p+r)/2 ，或者取这三个元素按照大小排序后的中间值。例子：a = 38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72，取(left+right)/2 处的元素作为分界点( pivot )的值。具体第一次分 区过程如下：iohi “ ht69|E|22 | 48 113 | 38 | 93 14 卩叭內冲In 衍- to Iohi| 69 | 5622* 48*

3、13*38-93*14 45 81 |1972*hilo ” * to| 69 5822 4813384514”93-81 |7972f牛因此，第一次分区，以69为分界点，结果为：a = 14, 58, 22, 48, 13, 38, 45, 69, 93, 81,79, 72二、实验代码#i nclude int fast_sort(int*a,int i,int j,int *p,int *b)int k,temp,f,g;g=*P；g=(12*g)-12;g=%dn,g);/in tf(成功进入快速排序 k=i;i+；for(;iak&ij;)j-;for(;aiak &i j;)i+;

4、/in tf(i=%dn,i);if(i=j)break;if(i*z)*z=*p;/prin tf(z=%dnp=%d,*z,*p);void main() int a=38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72;int b1012;int y=0,k,x=0,z=0;prin tf(初始序列为);for(k=0;k12;k+)prin tf(%3d,ak);prin tf(n);digui(a,0,11, &x,b, &z);for(y=1;yz+1;y+)printf(第%2d次后的数组为,y);prin tf(%3d,by-1k); p

5、rin tf(n);三、实验数据（给出实验结果）对序列 a = 38, 81,22, 48, 13, 69, 93, 14, 45, 58, 79, 7238 81 22 48 13 69 93 14 45 58 79 7238 14 22 48 13 69 9381 45 58 79 7238 14 2213 48 69 93 81 45 58 79 72址】吃后賞垃淤吋 第7次后的额为 却3汰年m：匙圣勺 X q底石的刪为t_es h any kn to1491 45 碣 79时 60 58 ?991 网 58 795$ 72 8L 7969 7? 79 81进行快速排序，其中，以序列的首

6、元素作为排序的分界点。输出结果 要求：输出每一次分区后的结果以及最终排序结果。13 14 2213 14 2213 14 22 CDCitime,38 4833 45刖4o38 4530 45 忙地im吐理中DMktofi囲山童快1樟弓瑰垦中- X四、实验总结（问题、解决方法、心得体会等） 这次实验我做了很久， 重新编写了算法很多次。 最开始我对算法的理 解不够深，在递归自调用的时候没有想通上下界其实在递归下一层的 时候下一层是知道上一层的上下界的， 只要排序算法里返还一个最好 作为比较值的位置就可以了。 一开始排序算法写完就把每次数输出出 来，知道后来和同学讨论正确答案是排序了多少次， 才想想到我是把 每个区排完后的情况， 而其实我想输出的是每次排序后数组情况。 可 是一开始进入的就是左半区的左半区的左半区。反正一次是无法 输出全部的，因为右半区还没有算。思考了很久，我决定建立一个二 维数组，第一行是第一次后的数组，第二行是第二次后的数组。可是 如何确定现在是第几次？我建立了一个指针， 每次进入递归一层就会 +