《分治算法实验》由会员分享，可在线阅读，更多相关《分治算法实验（6页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计实验报告第四次附加实验姓名时间学号班级工训楼30912.26上午地点实验名称分治算法实验（用分治法实现快速排序算法）实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。给定任意几组数据，利用分治法的思想，将数据进行快速排序并将排好的数据 进行输出。程序思想：通过一趟排序将要排序的数据分割成独立的两部分，实验原理据都比另外一部分的所有数据都要小，其中一部分的所有数然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法的性能取决于划分的对称性。通过修改函数设计出采用随机选择策略的快速排序算法。Parti
2、tion，可以分解：以ap为基准兀素将ap:r划分成3段ap:q-1，aq和aq+1:r，使ap:q-1中任何一个元素小于等于实验步骤于aq。下标q在划分过程中确定。递归求解：通过递归调用快速排序算法分别对aq，而aq+1:r中任何一个元素大于等ap:q-1和aq+1:r进行排序。ap:q-1和ap:r就已排好序。合并：由于对ap:q-1和aq+1:r的排序是就地进行的，所以在aq+1:r都已排好的序后，不需要执行任何计算，/函数 Partition以一个确疋的基准兀素 ap对子数组 ap:r进行划分template int Partition(Type a,关键代码int p, int r)
3、int i = p,j = r + 1;Type x = ap;/将乂的元素交换到右边区域while (true )while (a+ix & ix); if (i=j)break;Swap(ai,aj);ap = aj;aj = x;return j;/通过 RandomizedPartition 函数来产生随机的划分 template vclassTypeint RandomizedPartition(Type a, int p, int r) int i = Random(p,r);Swap(ai,ap);return Partition(a,p,r);/将基准元素放在合适的位置较小个数
4、排序序列的结果:测试结果较大个数排序序列的结果:序审序灵亍熱11 61 31 88 2B 25 75 ?511 61 31 88 2B 25 75 ?579 56 64 46 88 9S 8B 15 21 2679 56 64 46 88 9S 8B 15 21 26 8383 J 69J 69 0 0 7171 84 41 7084 41 70 S S3 75 C9 52 31 74 243 75 C9 52 31 74 24 6969 Lfi 69Lfi 69 2626 3 3 G G G G ?3 91 2S 2B?3 91 2S 2B心41 941 9B B 3 b3 b 6 S ?6
5、 S ? 1111 lblb 1H 211H 21 2121聽2b2b ZfeZfe Z#Z#姑跖31 dl31 dl 4141 13 4b13 4b吕盘!&6969盟6? 7B 70 716? 7B 70 71 7373 7474 7979 7?7? 3 3 8 8J J 84 WE 08 9B ?184 WE 08 9B ?1 3 9S3 9SThe Cine it B.20The Cine it B.20请按任意融绒b!b!快速排序在之前的数据结构中也是学过的， 在几大排序算法中，快速排序和归 并排序尤其是重中之重，之前的快速排序都是给定确定的轴值， 所以存在一些 极端的情况使得时间复杂
6、度很高， 排序的效果并不是很好， 现在学习的一种利 用随机化的快速排序算法，通过随机的确实验心得定轴值，从而可以期望划分是较对称的，减少了出现极端情况的次数，使得排序的效率挺高了很多，通过这一次的与后面的随机 实验和自己的化算法想呼应，而且关键的是对于随机生成函数，学习终于弄明白是怎么回事了，不错。实验得分助教签名更大个数排序序列的结果:附录：完整代码(分治法)/随机后标记元素后的快速排序#i nclude #in elude /定义int a1000000;全局#inelude #include using namespacestd;template void S &x,Type &y);/
7、 声明 swap 函数inlineint Random(int x, int y);template int Partition(Type a,/ 声明内联函数int p, int r);/ 声明 Partition函数template int RandomizedPartition(Type a, int p, int r); / 声明 RandomizedPartition 函数template void RandomizedQuickSort(Type a, int p, int r); / 声明 RandomizedQuickSort 函数void ran( int *input, i
8、nt n) / 随机生成数组元素函数int i;srand(time(0);for (i=0;in;i+) inputi=rand()%100; / 生成的数据在 0100 之间 inputi= 0 ;int main()int n;cout 请输入要排序的序列个数： n; / 输入要排序的序列个数ran(a,n); / 随机生成数组 afor (int i=0; in; i+) / 先将要排序的数组输出 coutai ;coutendl;coutendl;clock_t start,end,over;start=clock();end=clock(); over=end-start;star
9、t=clock();/ 计算程序运行时间的算法/ 调用随机化的快速排序 RandomizedQuickSort 函数RandomizedQuickSort(a,0,n-1);for (int i=0; in; i+) coutai ; coutendl;end=clock();/ 输出排序好的结果printf( The time is %6.3f 示,( double )(end-start-over)/CLK_TCK);运行时间coutendl;system( pause );return 0;/ 显template void S &x,Type &y) / 将两个数据交换Type temp
10、 = x; x = y;y = temp;/函数产生x和y之间的一个随机整数， 且产生不同整数的概率相同 inline int Random(intx, int y)srand( unsigned )time(0);int ran_num = rand() % (y - x) + x;return ran_num;/函数 Partition以一个确定的基准元素 ap对子数组 ap:r进行划分template int Partition(Type a, int p, int r)int i = p,j = r + 1;Type x = ap;/将x 的元素交换到左边区域/将之的元素交换到右边区域
11、 while (true )while (a+ix & ix);if (i=j) break;Swap(ai,aj);ap = aj;aj = x; return j;/ 将基准元素放在合适的位置/ 通过 RandomizedPartition 函数来产生随机的划分 template int RandomizedPartition(Type a,int p, int r)int i = Random(p,r);Swap(ai,ap);return Partition(a,p,r);template void RandomizedQuickSort(Type a, int p, int r)if (pr)int q = RandomizedPartition(a,p,r);RandomizedQuickSort(a,p,q-1);RandomizedQuickSort(a,q+1,r);/ 获得基准元素的位置/ 对左半段排序/ 对右半段排序
