算法分析与设计实验一

《算法分析与设计实验一》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法分析与设计》实验报告专业：计科班级：日期：2016/04/11成绩:学生姓名：学号：指导老师：实验单元一递归设计一、实验题目实验一排序二、实验目的熟悉java语言(或C++)的集成开发环境；通过两种利用分治算法求解的排序算法来加深对递归设计和分治算法的理解。三、实验内容掌握递归算法的概念和基本思想，分析并掌握排列问题的递归算法。对于一个序列，使用快速排序算法和归并排序算法对其实现排序。四、实验结果（代码及运行结果）(一)快速排序源代码：publicclassQuickSort{publicstaticvoidmain(Strin

2、g[]args){int[]data=newint[]{5,3,6,2,1,9,4,8,7};print(data);quickSort(data,0,data.length-1);//调用快速排序方法System.out.println("排序后的数组：");//打印输入函数print(data);}/***交换i、j位置数组中的内容（替代了新建临时变量）*/publicstaticvoidswap(int[]data,inti,intj){if(i==j){return;}data[i]=data[i]+data[j];data[

3、j]=data[i]-data[j];data[i]=data[i]-data[j];}/***快速排序核心方法*/7publicstaticvoidquickSort(int[]data,intstart,intend){if(start>=end)//排除数组中仅有一个元素的情况return;//以起始索引为分界点intpivot=data[start];inti=start+1;intj=end;while(true){while(i<=end&&data[i]

4、t的元素，下标加1}while(j>start&&data[j]>pivot){j--;//从数组最后一个元素开始,凡大于pivot的元素，下标减1}if(i

5、ticvoidprint(int[]data){for(inti=0;i

6、5,3,6,2,9,4,7};System.out.print("排序前：t");print(data);mergeSort(data);//调用归并排序方法System.out.print("排序后：t");print(data);}/***归并排序方法mergeSort*/publicstaticvoidmergeSort(int[]data){sort(data,0,data.length-1);}/***排序方法*/publicstaticvoidsort(int[]data,intleft,intright){if(le

7、ft>=right)//如果数组中只有一个元素，则无须操作。返回空7return;intcenter=(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个数组已有序，归并后依然有序**@paramda

8、ta数组对象*@paramleft左数组的第一个元素的索引*@paramcenter左数组的最后一个元素的索引，center+1是右数组第一个元素的索引*@paramright右数组最后一个元素的索引*/publicst