算法分析与设计实验报告
第四次附加实验
姓名 时间 学号 班级 工训楼309 12.26上午 地点 实验名称 分治算法实验（用分治法实现快速排序算法） 实验目的 通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。 给定任意几组数据，利用分治法的思想，将数据进行快速排序并将排好的数据 进行输出。 程序思想： 通过一趟排序将要排序的数据分割成独立的两部分， 实验原理 据都比另外一部分的所有数据都要小， 其中一部分的所有数 然后再按此方法对这两部分数据分别进 行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 快速排序算法的性能取决于划分的对称性。通过修改函数 设计出采用随机选择策略的快速排序算法。 Partition，可以 分解：以a[p]为基准兀素将a[p:r]划分成3段a[p:q-1]，a[q]和a[q+1:r]，使 a[p:q-1]中任何一个元素小于等于 实验步骤 于a[q]。下标q在划分过程中确定。 递归求解：通过递归调用快速排序算法分别对 a[q]，而a[q+1:r]中任何一个元素大于等 a[p:q-1]和a[q+1:r]进行排序。 a[p:q-1]和 a[p:r]就已排好序。 合并：由于对 a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在 a[q+1:r]都已排好的序后，不需要执行任何计算， //函数Partition 以一个确疋的基准兀素a[p]对子数组a[p:r]进行 划分 template < class Type> int Partition(Type a[], int p, int r) { 关键代码 int i = p,j = r + 1; Type x = a[p]; //将 while (a[--j]>x); if (i>=j) { break; } Swap(a[i],a[j]); } a[p] = a[j]; a[j] = x; return j; } //通过RandomizedPartition函数来产生随机的划分 template vclass Type> int RandomizedPartition(Type a[], int p, int r) { int i = Random(p,r); Swap(a[i],a[p]); return Partition(a,p,r); } //将基准元素放在合适的位置 较小个数排序序列的结果: 测试结果 较大个数排序序列的结果: 序审序灵亍熱 11 61 31 88 2B 25 75 ?5 79 56 64 46 88 9S 8B 15 21 26 83 J 69 0 71 84 41 70 S 3 75 C9 52 31 74 24 69 Lfi 69 26 3 G G ?3 91 2S 2B 心 41 9 B 3 b 6 S ? 11 lb 1H 21 21 聽 2b Zfe Z# 姑跖 31 dl 41 13 4b 吕盘!>& 69 盟 6? 7B 70 71 73 74 79 7? ?3 8J 84 WE 08 9B ?1 ?3 9S The Cine it B.@20 请按任意融绒■…■b! 快速排序在之前的数据结构中也是学过的， 在几大排序算法中，快速排序和归 并排序尤其是重中之重，之前的快速排序都是给定确定的轴值， 所以存在一些 极端的情况使得时间复杂度很高， 排序的效果并不是很好， 现在学习的一种利 用随机化的快速排序算法，通过随机的确实验心得 定轴值，从而可以期望划分是较对称 的，减少了出现极端情况的次数， 使得排序的效率挺高了很多， 与后面的随机 实通过这一次的 验和自己的 化算法想呼应，而且关键的是对于随机生成函数， 学习终于弄明白是怎么回事了，不错。 实验得分 助教签名 更大个数排序序列的结果: 附录： 完整代码(分治法) //随机后标记元素后的快速排序 #i nclude #inelude int a[1000000]; template < class Type> void S &x,Type &y); //定义全局变量用来存放要查找的数组 // 声明swap函数 // 声明内联函数 inline int Random(int x, int y); template < class Type> int Partition(Type a[], int p, int r); template // 声明 Partition 函数 int RandomizedPartition(Type a[], int p, int r); // 声明 RandomizedPartition 函数
分治算法实验(用分治法实现快速排序算法)
