Java常用基本算法.doc

《Java常用基本算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.1算法前面我们已经讲过，程序=数据结构+算法。什么是算法？对一个现有的问题我们采取的解决过程及方法，即为算法。一个用算法实现的程序会耗费两种资源：处理时间和内存。算法的效率分析标准：时间复杂度空间复杂度简单性和清晰性对于时间复杂度，可以通过System.currentTimeMillis()方法来测试。例如：publicclassTest{publicstaticvoidmain(Stringargs[]){System.out.println(System.currentTimeMillis());fun();System.out.prin

2、tln(System.currentTimeMillis());}publicstaticvoidfun(){doublea=0;for(inti=0;i<10000;i++)for(intj=0;j<10000;j++)for(intk=0;k<100;k++)a++;}}前后两次获得当前系统时间的差值就是运行所消耗的时间（毫秒为单位）。通过System.currentTimeMillis()方法来测试的缺点：a.不同的平台执行的时间不同b.有些算法随着输入数据的加大，测试时间会变得不切实际！4.2查找4.2.1查找之线性查找（直接查找）算法思

3、路：从数组的第一个元素开始查找，并将其与查找值比较，如果相等则停止，否则继续下一个元素查找，直到找到匹配值。注意：被查找的数组中的元素可以是无序的、随机的。实例：importjava.util.*;publicclassDemo1{publicstaticvoidmain(Stringargs[]){intiArr[]={32,9,78,44,29,18,97,49,56,61};System.out.println("数组的所有元素为：");for(inti:iArr)System.out.print(i+"");System.out.prin

4、tln();System.out.print("请输入你要查找的元素：");Scannerscan=newScanner(System.in);intiNum=scan.nextInt();intindex=straightSearch(iArr,iNum);if(index==-1)System.out.println("没有找到元素"+iNum);elseSystem.out.println("找到元素"+iNum+",下标为:"+index);}publicstaticintstraightSearch(int[]arr,intnum){i

5、nti=0;for(;i

6、importjava.util.*;publicclassDemo1{publicstaticvoidmain(Stringargs[]){intiArr[]={1,2,3,4,6,8,22,44,99,111,112,116};System.out.println("数组的所有元素为：");for(inti:iArr)System.out.print(i+"");System.out.println();System.out.print("请输入你要查找的元素：");Scannerscan=newScanner(System.in);intiN

7、um=scan.nextInt();intindex=binarySearch(iArr,iNum,0,iArr.length-1);if(index==-1)System.out.println("没有找到元素"+iNum);elseSystem.out.println("找到元素"+iNum+",下标为:"+index);}publicstaticintbinarySearch(int[]arr,intnum,intiMin,intiMax){while(iMin<=iMax){intiMid=(iMin+iMax)/2;if(num==ar

8、r[iMid])returniMid;elseif(num