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

算法分析与设计实验报告第 四 次附加实验姓名学号班级时间12.26上午地点工训楼309 实验名称分治算法实验(用分治法实现快速排序算法)实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用分治法的思想，将数据进行快速排序并将排好的数据进行输出。程序思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序算法的性能取决于划分的对称性。通过修改函数Partition，可以设计出采用随机选择策略的快速排序算法。实验步骤 分解：以ap为基准元素将ap:r划分成3段ap:q-1，aq和aq+1:r，使ap:q-1中任何一个元素小于等于aq，而aq+1:r中任何一个元素大于等于aq。下标q在划分过程中确定。 递归求解：通过递归调用快速排序算法分别对ap:q-1和aq+1:r进行排序。 合并：由于对ap:q-1和aq+1:r的排序是就地进行的，所以在ap:q-1和aq+1:r都已排好的序后，不需要执行任何计算，ap:r就已排好序。关键代码/函数Partition以一个确定的基准元素ap对子数组ap:r进行划分template int Partition(Type a,int p,int r) int i = p,j = r + 1; Type x = ap; /将x的元素交换到右边区域 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); 测试结果较小个数排序序列的结果： 较大个数排序序列的结果： 更大个数排序序列的结果： 实验心得快速排序在之前的数据结构中也是学过的，在几大排序算法中，快速排序和归并排序尤其是重中之重，之前的快速排序都是给定确定的轴值，所以存在一些极端的情况使得时间复杂度很高，排序的效果并不是很好，现在学习的一种利用随机化的快速排序算法，通过随机的确定轴值，从而可以期望划分是较对称的，减少了出现极端情况的次数，使得排序的效率挺高了很多，与后面的随机化算法想呼应，而且关键的是对于随机生成函数，通过这一次的实验和自己的学习终于弄明白是怎么回事了，不错。实验得分助教签名附录：完整代码（分治法）/ 随机后标记元素后的快速排序 #include #include #include#includeusing namespace std; int a; /定义全局变量用来存放要查找的数组template void Swap(Type &x,Type &y); /声明swap函数 inline int 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,int 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); /随机生成数组a for(int i=0; in; i+) /先将要排序的数组输出 coutai ; coutendl;coutendl;clock_t start,end,over; /计算程序运行时间的算法start=clock();end=clock();over=end-start;start=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 Swap(Type &x,Type &y) /将两个数据交换 Type temp = x; x = y; y = temp; /函数产生x和y之间的一个随机整数，且产生不同整数的概率相同 inline int Random(int x, 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的元素交换到右边区域 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