算法分析与设计实验一样本.docx

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。算法分析与设计实验报告专业: 计科 班级: 日期: /04/11 成绩: 学生姓名: 学号: 指导老师: 实验单元一 递归设计一、 实验题目 实验一 排序二、 实验目的熟悉java语言(或C+)的集成开发环境; 经过两种利用分治算法求解的排序算法来加深对递归设计和分治算法的理解。三、 实验内容掌握递归算法的概念和基本思想, 分析并掌握排列问题的递归算法。对于一个序列, 使用快速排序算法和归并排序算法对其实现排序。四、 实验结果( 代码及运行结果) (一) 快速排序源代码: public class QuickSort public static void main(String args) int data = new int 5, 3, 6, 2, 1, 9, 4, 8, 7 ;print(data);quickSort(data, 0, data.length - 1); / 调用快速排序方法System.out.println(排序后的数组: ); / 打印输入函数print(data);/* * 交换i、 j位置数组中的内容( 替代了新建临时变量) */public static void swap(int data, int i, int j) if (i = j) return;datai = datai + dataj;dataj = datai - dataj;datai = datai - dataj;/* * 快速排序核心方法*/public static void quickSort(int data, int start, int end) if (start = end) / 排除数组中仅有一个元素的情况return;/ 以起始索引为分界点int pivot = datastart;int i = start + 1;int j = end;while (true) while (i = end & datai start & dataj pivot) j-; / 从数组最后一个元素开始,凡大于pivot的元素, 下标减1if (i j) / 经过上面的操作, datai大于pivot, dataj小于pivot, 因此交换i、 j中的内容swap(data, i, j); else break;swap(data, start, j);print(data);quickSort(data, start, j - 1); / 递归左子序列quickSort(data, j + 1, end); / 递归右子序列public static void print(int data) for (int i = 0; i = right) / 如果数组中只有一个元素, 则无须操作。返回空return;int center = (left + right) / 2; / 求中间索引sort(data, left, center); / 1、 左递归sort(data, center + 1, right); / 2、 右递归merge(data, left, center, right); / 3、 合并System.out.print(第 + (count+) + 递归t);print(data); / 打印输出数组/* * 归并方法, 归并前面2个数组已有序, 归并后依然有序 * * param data 数组对象 * param left 左数组的第一个元素的索引 * param center 左数组的最后一个元素的索引, center+1是右数组第一个元素的索引 * param right 右数组最后一个元素的索引 */public static void merge(int data, int left, int center, int right) int temp = new intdata.length; / 经过new关键字, 在堆上创立临时数组int middle = center + 1; / 右数组第一个元素索引int k = left; / k记录临时数组的索引int tmp = left; / 缓存左数组第一个元素的索引while (left = center & middle = right) if (dataleft = datamiddle) / 从两个数组中取出最小的放入临时数组tempk+ = dataleft+; else tempk+ = datamiddle+;while (middle = right) / 剩余部分依次放入临时数组( 实际上两个while只会执行其中一个) tempk+ = datamiddle+;while (left = center) tempk+ = dataleft+;while (tmp = right) / 将临时数组中的内容拷贝回原数组中datatmp = temptmp+;public static void print(int data) for (int i = 0; i data.length; i+) System.out.print(datai + t);System.out.println();运行结果: 2.1 归并排序算法运行结果-异常2.2 异常原因-导入多余的包2.3 归并排序算法运行正确结果显示3.1 快速、 归并排序算法文件五、 实验体会合并排序: 用分治策略实现对n个元素进行排序的算法。基本思想: 将待排序元素分成大小大致相同的两个子集合, 分别对两个子集合进行排序, 最终将排序好的子集合合并成所要求的排好序的集合。快速排序: 基于分治策略的另一个排序算法。基本思想: 对于输入的子数组ap:r, 按以下三个步骤进行排序: ( 1) 分解( Divide) : 以ap为基准元素将ap:r划分成3段ap:q-1,aq,aq+1:r,使ap:q-1中的任何一个元素小于等于aq, 而aq+1:r中任何一个元素大于等于aq。下标q在划分过程中确定。( 2) 递归求解( Conquer) : 利用递归调用快速排序算法分别对ap:q-1和aq+1:r进行排序。( 3) 合并( Merge) : 由于对ap:q-1和aq+1:r的排序是就地进行的, 因此在ap:q-1和aq+1:r都已经排好的序后, 不需要执行任何计算,ap:r就已经排好序。心得体会: 学习初衷: 在大三接触这门选修课, 不知道算早还是晚。现实中, 已经面临就业的问题, 其实以前也想过补充自己关于算法方面的知识。可是一直没有挤出时间、 更确切地说拿出勇气去研究一些算法。正好, 在毕业之际, 选了这门课, 经过实验能够更好地掌握关于算法方面的一些基本知识。实验过程: 实验进行的并不是很顺利, 由于长时间没有编这种有关算法的程序( 或者说是几乎没有编过) , 因此消耗了近一个中午仍旧没有什么进展。虽然自己也写了一百行代码。就如同老师说的那样, 出错率很高, 特别是逻辑上的错误。例如: 数组下表越界、 出程序逻辑太混乱等。难题解决: 经过复习教材22-26页关于合并、 快速排序算法的概念, 以及在晚上查阅一些资料。自己在eclipse中完成两个小实验。经过这次实验, 自己了解到了归并、 快速排序算法以及分治思想。经过对比学习了归并和快速的异同。虽然没有自己亲手编写出来那份难以抑制的激动, 可是学到了( 熟悉了) 关于算法方面的知识, 进步的我还是很欣慰。希望经过这门课以及自己按时完成实验, 为自己以后打下一些基础!