分治算法实验(用分治法实现快速排序算法).doc

《分治算法实验(用分治法实现快速排序算法).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析与设计实验报告第四次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称分治算法实验(用分治法实现快速排序算法)实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用分治法的思想，将数据进行快速排序并将排好的数据进行输出。程序思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法的性能取决于划分的对称性。通过修改函数Partition，可以设计出采用随机选择策略的快

2、速排序算法。实验步骤①分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1]，a[q]和a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。②递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。③合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。关键代码//函数Partition以一个确定的基准元素a[p]对子数组a[p:r]进行划分templat

3、eintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将x的元素交换到右边区域while(true){while(a[++i]x);if(i>=j){break;}Swap(a[i],a[j]);}a[p]=a[j];//将基准元素放在合适的位置a[j]=x;returnj;}//通过RandomizedPartition函数来产生随机的划分templateintRandomizedPartition(Typea

4、[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}测试结果较小个数排序序列的结果：较大个数排序序列的结果：更大个数排序序列的结果：实验心得快速排序在之前的数据结构中也是学过的，在几大排序算法中，快速排序和归并排序尤其是重中之重，之前的快速排序都是给定确定的轴值，所以存在一些极端的情况使得时间复杂度很高，排序的效果并不是很好，现在学习的一种利用随机化的快速排序算法，通过随机的确定轴值，从而可以期望划分是较对称的，减少了出现极端情况的次数，使得排序的效率挺高了很多，与后面的随机化算法想呼应，而且关键的是对于

5、随机生成函数，通过这一次的实验和自己的学习终于弄明白是怎么回事了，不错。实验得分助教签名附录：完整代码（分治法）//随机后标记元素后的快速排序#include#include#include#includeusingnamespacestd;inta[];//定义全局变量用来存放要查找的数组templatevoidSwap(Type&x,Type&y);//声明swap函数inlineintRandom(intx,inty);//声明内联函数templateintPartition(

6、Typea[],intp,intr);//声明Partition函数templateintRandomizedPartition(Typea[],intp,intr);//声明RandomizedPartition函数templatevoidRandomizedQuickSort(Typea[],intp,intr);//声明RandomizedQuickSort函数voidran(int*input,intn)//随机生成数组元素函数{inti;srand(time(0));for(i=0;i

7、/生成的数据在0~100之间input[i]='';}intmain(){intn;cout<<"请输入要排序的序列个数："<>n;//输入要排序的序列个数ran(a,n);//随机生成数组afor(inti=0;i