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

算法分析与设计实验报告第四次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称分治算法实验(用分治法实现快速排序算法)实验目的通过上机实验要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据利用分治法的思想将数据进行快速排序并将排好的数据进行输出。程序思想：通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。快速排序算法的性能取决于划分的对称性。通过修改函数Partition可以设计出采用随机选择策略的快速排序算法。实验步骤分解：以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]进行划分template<classType>intPartition(Typea[]intpintr){inti=pj=r+1;Typex=a[p];//将<x的元素交换到左边区域//将>x的元素交换到右边区域while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j){break;}Swap(a[i]a[j]);}a[p]=a[j];//将基准元素放在合适的位置a[j]=x;returnj;}//通过RandomizedPartition函数来产生随机的划分template<classType>intRandomizedPartition(Typea[]intpintr){inti=Random(pr);Swap(a[i]a[p]);returnPartition(apr);}测试结果较小个数排序序列的结果：较大个数排序序列的结果：更大个数排序序列的结果：实验心得快速排序在之前的数据结构中也是学过的在几大排序算法中快速排序和归并排序尤其是重中之重之前的快速排序都是给定确定的轴值所以存在一些极端的情况使得时间复杂度很高排序的效果并不是很好现在学习的一种利用随机化的快速排序算法通过随机的确定轴值从而可以期望划分是较对称的减少了出现极端情况的次数使得排序的效率挺高了很多与后面的随机化算法想呼应而且关键的是对于随机生成函数通过这一次的实验和自己的学习终于弄明白是怎么回事了不错。实验得分助教签名附录：完整代码（分治法）//随机后标记元素后的快速排序#include<iostream>#include<ctime>#include<time.h>#include<iomanip>usingnamespacestd;inta[1000000];//定义全局变量用来存放要查找的数组template<classType>voidSwap(Type&xType&y);//声明swap函数inlineintRandom(intxinty);//声明内联函数template<classType>intPartition(Typea[]intpintr);//声明Partition函数template<classType>intRandomizedPartition(Typea[]intpintr);//声明RandomizedPartition函数template<classType>voidRandomizedQuickSort(Typea[]intpintr);//声明RandomizedQuickSort函数