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

算法分析与设计实验报告算法分析与设计实验报告 第第 四四 次附加实验次附加实验 姓名学号班级 时间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 int Partition Type a int p int r int i p j r 1 Type x 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 return j 通过RandomizedPartition函数来产生随机的划分 template int RandomizedPartition Type a int p int r int i Random p r Swap a i a p return Partition a p r 测试结果 较小个数排序序列的结果 较大个数排序序列的结果 附录 附录 完整代码 分治法 完整代码 分治法 随机后标记元素后的快速排序 include include include include using namespace std int a 定义全局变量用来存放要查找的数组 template void Swap Type 声明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 i n i input i rand 100 生成的数据在0 100之间 input i 0 int main int n cout 请输入要排序的序列个数 n 输入要排序的序列个数 ran a n 随机生成数组a for int i 0 i n i 先将要排序的数组输出 cout a i cout endl cout endl clock t start end over 计算程序运行时间的算法 start clock end clock over end start start clock 调用随机化的快速排序RandomizedQuickSort函数 RandomizedQuickSort a 0 n 1 for int i 0 i n i 输出排序好的结果 cout a i cout endl end clock printf The time is 6 3f double end start over CLK TCK 显示运行时间 cout endl system pause return 0 template void Swap Type 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以一个确定的基准元素a p 对子数组a p r 进行划分 template int Partition Type a int p int r int i p j r 1 Type x 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 return j 通过RandomizedPartition函数来产生随机的划分 template int RandomizedPartition Type a int p int r int i Random p r Swap a i a p return Partition a p r template void RandomizedQuickSo