算法分析与设计实验一

1 算法分析与设计算法分析与设计 实验报告实验报告 专业专业 计科 班级 班级 日期 日期 2016 04 11 成绩成绩 学生姓名 学生姓名 学号 学号 指导老师 指导老师 实验单元一实验单元一 递归设计递归设计 一 一 实验题目实验题目 实验一 排序 二 二 实验目的实验目的 熟悉 java 语言 或 C 的集成开发环境 通过两种利用分治算法求解的排序算法来加深对递归设 计和分治算法的理解 三 三 实验内容实验内容 掌握递归算法的概念和基本思想 分析并掌握排列问题的递归算法 对于一个序列 使用快速排 序算法和归并排序算法对其实现排序 四 四 实验结果 代码及运行结果 实验结果 代码及运行结果 一一 快速排序源代码 快速排序源代码 publicpublic classclass QuickSort publicpublic staticstatic voidvoid main String args intint data newnew intint 5 3 6 2 1 9 4 8 7 print data quickSort data 0 data length 1 调用快速排序方法 System outout println 排序后的数组 打印输入函数 print data 交换i j位置数组中的内容 替代了新建临时变量 publicpublic staticstatic voidvoid swap intint data intint i intint j ifif i j returnreturn data i data i data j data j data i data j data i data i data j 快速排序核心方法 2 publicpublic staticstatic voidvoid quickSort intint data intint start intint end ifif start end 排除数组中仅有一个元素的情况 returnreturn 以起始索引为分界点 intint pivot data start intint i start 1 intint j end whilewhile truetrue whilewhile i end 从数组最后一个元素开始 凡大于pivot的元素 下标减1 ifif i j 经过上面的操作 data i 大于pivot data j 小于pivot 所以交换 i j中的内容 swap data i j elseelse breakbreak swap data start j print data quickSort data start j 1 递归左子序列 quickSort data j 1 end 递归右子序列 publicpublic staticstatic voidvoid print intint data forfor intint i 0 i right 如果数组中只有一个元素 则无须操作 返回空 4 returnreturn intint center left right 2 求中间索引 sort data left center 1 左递归 sort data center 1 right 2 右递归 merge data left center right 3 合并 System outout print 第 count 递归 t print data 打印输出数组 归并方法 归并前面2个数组已有序 归并后依然有序 param param data 数组对象 param param left 左数组的第一个元素的索引 param param center 左数组的最后一个元素的索引 center 1是右数组第一个元素的索 引 param param right 右数组最后一个元素的索引 publicpublic staticstatic voidvoid merge intint data intint left intint center intint right intint temp newnew intint data length 通过new关键字 在堆上创建临时数组 intint middle center 1 右数组第一个元素索引 intint k left k记录临时数组的索引 intint tmp left 缓存左数组第一个元素的索引 whilewhile left center elseelse temp k data middle whilewhile middle right 剩余部分依次放入临时数组 实际上两个while只 会执行其中一个 temp k data middle whilewhile left center temp k data left whilewhile tmp right 将临时数组中的内容拷贝回原数组中 data tmp temp tmp publicpublic staticstatic voidvoid print intint data forfor intint i 0 i data length i System outout print data i t 5 System outout println 运行结果 运行结果 2 1 归并排序算法运行结果 异常 6 2 2 异常原因 导入多余的包 2 3 归并排序算法运行正确结果显示 3 1 快速 归并排序算法文件 7 五 实验体会五 实验体会 合并排序 合并排序 用分治策略分治策略实现对 n 个元素进行排序的算法 基本思想 将待排序元素分成 大小大致相同的两个子集合两个子集合 分别对两个子集合进行排序 最终将排序好的子集合合并成所将排序好的子集合合并成所 要求的排好序的集合要求的排好序的集合 快速排序 快速排序 基于分治策略的另一个排序算法 基本思想 对于输入的子数组 a p r 按 以下三个步骤进行排序 1 分解 分解 DivideDivide 以 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 在划分过程中确定 2 递归求解 递归求解 ConquerConquer 利用递归调用快速排序算法分别对 a p q 1 和 a q 1 r 进行 排序 3 合并 合并 MergeMerge 由于对 a p q 1 和 a q 1 r 的排序是就地进行的 所以在 a p q 1 和 a q 1 r 都已经排好的序后 不需要执行任何计算 a p r 就已经排好序 心得体会 学习初衷 学习初衷 在大三接触这门选修课 不知道算早还是晚 现实中 已经面临就业的问题 其实以前 也想过补充自己关于算法方面的知识 可是一直没有挤出时间 更确切地说拿出勇气去研究一些算法 正好 在毕业之际 选了这门课 通过实验可以更好地掌握关于算法方面的一些基本知识 实验过程 实验进行的并不是很顺利 由于长时间没有编这种有关算法的程序 或者说是几乎没有编过 所以 消耗了近一个中午仍旧没有什么进展 虽然自己也写了一百行代码 就如同老师说的那样 出错率很高 尤其是逻辑上的错误 例如 数组下表越界 出程序逻辑太混乱等 难题解决 通过复习教材 22 26 页关于合并 快速排序算法的